# Question
Title: Most creative way to reverse a positive integer
Provided an input as an unsigned integer:

```
13457

```

Your function/subroutine should return:

```
75431

```

Since this is a popularity contest, be creative. Creative solutions use unusual or clever techniques to accomplish given task.

Constraints:

* You cannot use arrays.
* You cannot use strings.
* No RTL Override (`&#8238`)

Brownie points for using creative arithmetics.

Since this is a popularity contest, I suggest not using the modulo (`%`) operator in your code.

**About Leading zeroes:**

If the input is:

```
12340

```

Then the output:

```
4321

```

would be acceptable.

# Answer
> 49 votes
## Mathematica, no modulo!

```
n = 14627;
length = Ceiling[Log[10, n]];
img = Rasterize[n, RasterSize -> 400, ImageSize -> 400];
box = Rasterize[n, "BoundingBox", RasterSize -> 400, ImageSize -> 400];
width = box[[1]]; height = box[[3]];
ToExpression[
 TextRecognize[
  ImageAssemble[
   ImageTake[img, {1, height}, #] & /@
    NestList[# - width/length &, {width - width/length, width},
     length - 1]]]]

```

Let's break it down.

First we use some "creative arithmetics" to find out how many digits are in the number: `length = Ceiling[Log[10, n]];`

Next, we Rasterize the number to a nice large image:

Now we query for the bounding box of that image, and populate the width and height (actually using the baseline offset instead of the image height, because MM adds some whitespace below the baseline in the image).

Next, NestList recursively subtracts the width of the image divided by the length of the string to enable ImageTake to pluck characters from the end of the image one by one, and those are reassembled by ImageAssemble to this image:

Then we pass that on to the TextRecognize function for optical character recognition, which at this image size and rasterization quality is able to impeccably recognize the final output and give us the integer:

```
72641

```

Logarithms and OCR - It's like chocolate and peanut butter!

### New and improved

This version pads out the number to deal with the obstinate behavior of TextRecognize with small numbers, and then subtracts out the pad at the end. This even works for single-digit numbers!

Though, why you would run a reverse routine on a single number is a mystery to me. But just for the sake of completeness, I even made it work for inputs of zero and one, which would normally break because the floored log doesn't return 1 for them.

```
n = 1;
pad = 94949;
length = If[n == 1 || n == 0, 1, Ceiling[Log[10, n]]];
img = Rasterize[n + (pad*10^length), RasterSize -> 400,
   ImageSize -> 400];
padlength = length + 5;
box = ImageDimensions[img];
width = box[[1]]; height = box[[2]];
reversed =
  ImageResize[
   ImageAssemble[
    ImageTake[img, {1, height}, #] & /@
     NestList[# - width/padlength &, {width + 1 - width/padlength,
       width}, padlength - 1]], 200];
recognized = ToExpression[TextRecognize[reversed]];
(recognized - pad)/10^5

```

# Answer
> 41 votes
## Perl/LuaTeX/Tesseract

The following Perl script reads the number as command line argument, e.g.:

`**1234567890**`

The following Perl script prints the number via LuaTeX. A virtual font is created on the fly that mirrors the digits horizontally.

>

Then the whole number is again mirrored horizontally:

>

The final image is reread via OCR (tesseract):

`**0987654321**`

```
#!/usr/bin/env perl
use strict;
$^W=1;

# Get the number as program argument or use a fixed number with all digits.
$_ = shift // 1234567890;

$\="\n"; # append EOL, when printing

# Catch negative number
exit print "NaUI (Not an Unsigned Integer)" if $_ < 0;

# Catch number with one digit.
exit ! print if ($_ = $= = $_) < 10;

undef $\;

# Write TeX file for LuaTeX
open(OUT, '>', 'temp.tex') or die "!!! Error: Cannot write: $!\n";
print OUT<<"END_PRINT";
% Catcode setting for iniTeX (a TeX format is not needed)
\\catcode`\{=1
\\catcode`\}=2
\\def\\mynumber{$_}
END_PRINT
print OUT<<'END_PRINT';
\directlua{tex.enableprimitives('',tex.extraprimitives())}
\pdfoutput=1 % PDF output
% move origin to (0,0)
\pdfhorigin=0bp
\pdfvorigin=0bp
% magnify the result by 5
\mag=5000

% Create virtual font, where the digits are mirrored
\directlua{
  callback.register('define_font',
    function (name,size)
      if name == 'cmtt10-digits' then
        f = font.read_tfm('cmtt10',size)
        f.name = 'cmtt10-digits'
        f.type = 'virtual'
        f.fonts = {{ name = 'cmtt10', size = size }}
        for i,v in pairs(f.characters) do
          if (string.char(i)):find('[1234567890]') then
            v.commands = {
               {'right',f.characters[i].width},
               {'special','pdf: q -1 0 0 1 0 0 cm'},
               {'char',i},
               {'right',-f.characters[i].width},
               {'special','pdf: Q'},
            }
          else
            v.commands = {{'char',i}}
          end
        end
      else
        f = font.read_tfm(name,size)
      end
      return f
    end
  )
}

% Activate the new font
\font\myfont=cmtt10-digits\relax
\myfont

% Put the number in a box and add a margin (for tesseract)
\dimen0=5bp % margin
\setbox0=\hbox{\kern\dimen0 \mynumber\kern\dimen0}
\ht0=\dimexpr\ht0+\dimen0\relax
\dp0=\dimexpr\dp0+\dimen0\relax
\pdfpagewidth=\wd0
\pdfpageheight=\dimexpr\ht0+\dp0\relax

% For illustration only: Print the number with the reflected digits:
\shipout\copy0 % print the number with the reflected digits

% Final version on page 2: Print the box with the number, again mirrored
\shipout\hbox{%
  \kern\wd0
  \pdfliteral{q -1 0 0 1 0 0 cm}%
  \copy0
  \pdfliteral{Q}%
}

% End job, no matter, whether iniTeX, plain TeX or LaTeX
\csname @@end\endcsname\end
END_PRINT

system "luatex --ini temp.tex >/dev/null";
system qw[convert temp.pdf temp%d.png];
system "tesseract temp1.png temp >/dev/null 2>&1";

# debug versions with output on console
#system "luatex --ini temp.tex";
#system qw[convert temp.pdf temp%d.png];
#system "tesseract temp1.png temp";

# Output the result, remove empty lines
open(IN, '<', 'temp.txt') or die "!!! Error: Cannot open: $!\n";
chomp, print while <IN>;
print "\n";
close(IN);

__END__

```

# Answer
> 25 votes
# **Brainfuck**

Basically, it is just an input-reversing program.

```
,[>,]<[.<]

```

UPD: As Sylwester pointed out in comments, in the classical Brainfuck interpreters/compilers (without possibility to going left from zero point in the memory array) this program would not work in the absence of '\>' at the beginning, so the more stable version is:

```
>,[>,]<[.<]

```

# Answer
> 20 votes
# Haskell

```
reverseNumber :: Integer -> Integer
reverseNumber x = reverseNumberR x e 0
    where e = 10 ^ (floor . logBase 10 $ fromIntegral x)

reverseNumberR :: Integer -> Integer -> Integer -> Integer
reverseNumberR 0 _ _ = 0
reverseNumberR x e n = d * 10 ^ n + reverseNumberR (x - d * e) (e `div` 10) (n + 1)
    where d = x `div` e

```

No arrays, strings, or modulus.

Also, I know we're not supposed to use lists or strings, but I love how short it is when you do that:

```
reverseNumber :: Integer -> Integer
reverseNumber = read . reverse . show

```

# Answer
> 18 votes
I suppose *someone* has to be the partypooper.

# Bash

```
$ rev<<<[Input]

```

```
$ rev<<<321
123
$ rev<<<1234567890
0987654321

```

Size limitations depend on your shell, but you'll be fine within reason.

# Answer
> 18 votes
## C++

```
/*
A one-liner RECUrsive reveRSE function. Observe that the reverse of a 32-bit unsigned int
can overflow the type (eg recurse (4294967295) = 5927694924 > UINT_MAX), thus the
return type of the function should be a 64-bit int.

Usage: recurse(n)
*/

int64_t recurse(uint32_t n, int64_t reverse=0L)
{
    return n ? recurse(n/10, n - (n/10)*10 + reverse * 10) : reverse;
}

```

# Answer
> 14 votes
## Javascript

**EDIT** : Since there is a suggestion to not use `%` operator, I use a little trick now.

I know this is not a code-golf, but there is no reason to make it longer.

```
function r(n){v=0;while(n)v=n+10*(v-(n=~~(n/10)));return v}

```

`r(13457)` returns `75431`

Moreover, it's a lot faster than *string* method (`n.toString().split('').reverse().join('')`) :

==\> JSPerf report \<==

# Answer
> 10 votes
## Python

*Not sure if this implementation qualifies for creative math*

*Also % operator was not used per se, though one might argue that divmod does the same, but then then the Question needs to be rephrased :-)*

**Implementation**

```
r=lambda n:divmod(n,10)[-1]*10**int(__import__("math").log10(n))+r(n /10)if n else 0

```

**demo**

```
>>> r(12345)
54321
>>> r(1)
1

```

**How does it work?**

*This is a recursive divmod solution* \*This solution determines the least significant digit and then pushes it to the end of the number.\*

**Yet Another Python Implementation**

```
def reverse(n):
    def mod(n, m):
        return n - n / m * m
    _len = int(log10(n))
    return n/10**_len + mod(n, 10)*10**_len + reverse(mod(n, 10**_len)/10)*10 if n and _len else n

```

**How does it work?**

*This is a recursive solution which swaps the extreme digits from the number*

```
Reverse(n) = Swap_extreme(n) + Reverse(n % 10**int(log10(n)) / 10)
             ; n % 10**log10(n) / n is the number without the extreme digits
             ; int(log10(n)) is the number of digits - 1
             ; n % 10**int(log10(n)) drops the most significant digit
             ; n / 10 drops the least significant digit

Swap_extreme(n) = n/10**int(log10(n)) + n%10*10**int(log10(n))
             ; n%10 is the least significant digit
             ; n/10**int(log10(n)) is the most significant digit

```

**Example Run**

```
reverse(123456) = 123456/10^5 + 123456 % 10 * 10^5 + reverse(123456 % 10 ^ 5 / 10)
                = 1           + 6 * 10 ^ 5 + reverse(23456/10)
                = 1           + 600000     + reverse(2345)
                = 600001 + reverse(2345)
reverse(2345)   = 2345/10^3 + 2345 % 10 * 10^3 + reverse(2345 % 10 ^ 3 / 10)
                = 2         + 5 * 10^3 + reverse(345 / 10)
                = 2         + 5000     + reverse(34)
                = 5002                 + reverse(34)
reverse(34)     = 34/10^1 + 34 % 10 * 10^1 + reverse(34 % 10 ^ 1 / 10)
                = 3       + 40             + reverse(0)
                = 43 + reverse(0)
reverse(0)      = 0

Thus

reverse(123456) = 600001 + reverse(2345)
                = 600001 + 5002 + reverse(34)
                = 600001 + 5002 + 43 + reverse(0)
                = 600001 + 5002 + 43 + 0
                = 654321

```

# Answer
> 9 votes
Just to be contrary, an overuse of the modulo operator:

```
unsigned int reverse(unsigned int n)
    {return n*110000%1099999999%109999990%10999900%1099000%100000;}

```

Note that this always reverses 5 digits, and 32 bit integers will overflow for input values more than 39045.

# Answer
> 8 votes
# **C#**

Here's a way to do it without the Modulus (`%`) operator and just simple arithmetic.

```
int x = 12356;
int inv = 0;
while (x > 0)
{
    inv = inv * 10 + (x - (x / 10) * 10);
    x = x / 10;
}
return inv;

```

# Answer
> 7 votes
Bash

```
> fold -w1 <<<12345 | tac | tr -d '\n'
54321

```

# Answer
> 6 votes
# C

```
#include <stdio.h>

int main(void) {
    int r = 0, x;
    scanf("%d", &x);
    while (x > 0) {
        int y = x;
        x = 0;
        while (y >= 10) { y -= 10; ++x; }
        r = r*10 + y;
    }
    printf("%d\n", r);
}

```

No strings, arrays, modulus or division. Instead, division by repeated subtraction.

# Answer
> 6 votes
# Mathematica

Making an image out of number, reflecting it, partitioning it into the digits. Then there is two alternatives:

1. Compare each image of a reflected digit with prepared earlier images, replace it with the corresponding digit and construct the number out of this.
2. Reflect every digit separately, construct a new image, and pass it to the image recognition function.

I did both

```
reflectNumber[n_?IntegerQ] :=
 ImageCrop[
  ImageReflect[
   Image@Graphics[
     Style[Text@NumberForm[n, NumberSeparator -> {".", ""}],
      FontFamily -> "Monospace", FontSize -> 72]],
   Left -> Right], {Max[44 Floor[Log10[n] + 1], 44], 60}]
reflectedDigits = reflectNumber /@ Range[0, 9];
reverse[0] := 0
reverse[n_?IntegerQ /; n > 0] :=
 Module[{digits},
  digits = ImagePartition[reflectNumber[1000 n], {44, 60}];
  {FromDigits[
    digits[[1]] /. (d_ :> # /; d == reflectedDigits[[# + 1]] & /@
       Range[0, 9])],
   ToExpression@
    TextRecognize[
     ImageAssemble[
      Map[ImageReflect[#, Left -> Right] &, digits, {2}]]]}]
reverse[14257893]
> {39875241, 39875241}

```

**EDIT**: Added padding of three zeroes, because `TextRecognise` works correctly only with integers \> 999.

# Answer
> 5 votes
# Lua

```
function assemble(n,...)
    if ... then
        return 10*assemble(...)+n
    end
    return 0
end
function disassemble(n,...)
    if n>0 then
        return disassemble(math.floor(n/10),n%10,...)
    end
    return ...
end
function reverse(n)
    return assemble(disassemble(n))
end

```

No arrays or strings used. The number is split into digits and reassembled using the arguments list.

# Answer
> 5 votes
## Python2

Assumes "unsigned integer" is 32-bit

```
import math
import sys
a=input()
p=int(math.log(a, 10))
b=a
while b%10==0:
    sys.stdout.write('0') # if 1-char string is not allowed, use chr(48) instead
    b=b/10

if p==0:
    print a
elif p==1:
    print a%10*10+a/10
elif p==2:
    print a%10*100+a%100/10*10+a/100
elif p==3:
    print a%10*1000+a%100/10*100+a%1000/100*10+a/1000
elif p==4:
    print a%10*10000+a%100/10*1000+a%1000/100*100+a%10000/1000*10+a/10000
elif p==5:
    print a%10*100000+a%100/10*10000+a%1000/100*1000+a%10000/1000*100+a%100000/10000*10+a/100000
elif p==6:
    print a%10*1000000+a%100/10*100000+a%1000/100*10000+a%10000/1000*1000+a%100000/10000*100+a%1000000/100000*10+a/1000000
elif p==7:
    print a%10*10000000+a%100/10*1000000+a%1000/100*100000+a%10000/1000*10000+a%100000/10000*1000+a%1000000/100000*100+a%10000000/1000000*10+a/10000000
elif p==8:
    print a%10*100000000+a%100/10*10000000+a%1000/100*1000000+a%10000/1000*100000+a%100000/10000*10000+a%1000000/100000*1000+a%10000000/1000000*100+a%100000000/10000000*10+a/100000000
elif p==9:
    print a%10*1000000000+a%100/10*100000000+a%1000/100*10000000+a%10000/1000*1000000+a%100000/10000*100000+a%1000000/100000*10000+a%10000000/1000000*1000+a%100000000/10000000*100+a%1000000000/100000000*10+a/1000000000

```

When given input `1230`, it outputs `0321`.

# Answer
> 4 votes
## Postscript

```
/rev{0 exch{dup 10 mod 3 -1 roll 10 mul add exch 10 idiv dup 0 eq{pop exit}if}loop}def

```

No arrays, no strings, no variables.

```
gs -q -dBATCH -c '/rev{0 exch{dup 10 mod 3 -1 roll 10 mul add exch 10 idiv dup 0 eq{pop exit}if}loop}def 897251 rev ='
152798

```

The same without `mod` (which is just a shortcut, so no big difference):

```
/rev {
    0 exch {
        dup
        10 idiv dup
        3 1 roll 10 mul sub
        3 -1 roll 10 mul add exch
        dup 0 eq {pop exit} if
    } loop
} def

```

# Answer
> 4 votes
# **C**

In that the obvious solution is represented in a couple other languages, might as well post it in C.

**Golfed:**

```
r;main(n){scanf("%d",&n);for(;n;n/=10)r=r*10+n%10;printf("%d",r);}

```

**Ungolfed:**

```
#include <stdio.h>

int main()
{
     int n, r = 0;
     scanf("%d", &n);
     for(;n;n/=10)
     {
          r = r * 10 + n % 10;
     }
     printf("%d", r);
}

```

EDIT: Just saw the modulus edit.

**Golfed (no modulus):**

```
r;main(n){scanf("%d",&n);for(;n;n/=10)r=r*10+(n-10*(n/10));printf("%d",r);}

```

**Ungolfed (no modulus):**

```
#include <stdio.h>

int main()
{
     int n, r, m = 0;
     scanf("%d", &n);
     for(;n;n/=10)
     {
          r=r*10+(n-10*(n/10));
     }
     printf("%d", r);
}

```

# Answer
> 4 votes
# C#

This uses no strings or arrays, but does use the .NET `Stack<T>` type (EDIT: originally used modulus operator; now removed)

```
public class IntegerReverser
{
    public int Reverse(int input)
    {
        var digits = new System.Collections.Generic.Stack<int>();
        int working = input;
        while (working / 10 > 0)
        {
            digits.Push(working - ((working / 10) * 10));
            working = working / 10;
        }
        digits.Push(working);
        int result = 0;
        int mult = 1;
        while (digits.Count > 0)
        {
            result += digits.Pop() * mult;
            mult *= 10;
        }
        return result;
    }
}

```

# Answer
> 4 votes
# python (easily done in assembly)

Reverses the bits of a byte. Points for not doing the exact same thing everyone else did?

```
x = int(input("byte: "), 2)
x = ((x * 8623620610) & 1136090292240) % 1023
print("{0:b}".format(x).zfill(8))

```

example

```
byte: 10101010
01010101

```

# Answer
> 4 votes
# Java

This is the this i've come up with, no strings, no arrays... not even variables (in Java I mind you):

```
public static int reverse(int n) {
    return n/10>0?(int)(modulo(n,10)*Math.pow(10, count(n)))+reverse(n/10):(int)(modulo(n,10)*Math.pow(10,count(n)));
}

public static int count(int i) {
    return (i = i/10)>0?count(i)+1:0;
}

public static int modulo(int i,int j) {
    return (i-j)>=0?modulo(i-j, j):i;
}

```

**EDIT** A more readable version

```
/** Method to reverse an integer, without the use of String, Array (List), and %-operator */
public static int reverse(int n) {
    // Find first int to display
    int newInt = modulo(n,10);
    // Find it's position
    int intPos = (int) Math.pow(10, count(n));
    // The actual value
    newInt = newInt*intPos;
    // Either add newInt to the recursive call (next integer), or return the found
    return (n/10>0) ? newInt+reverse(n/10) : newInt;
}

/** Use the stack, with a recursive call, to count the integer position */
public static int count(int i) {
    return (i = i/10)>0?count(i)+1:0;
}

/** A replacement for the modulo operator */
public static int modulo(int i,int j) {
    return (i-j)>=0?modulo(i-j, j):i;
}

```

# Answer
> 3 votes
# PowerShell

A quick solution in PowerShell. No arrays or strings used, either implicitly or explicitly.

```
function rev([int]$n) {
    $x = 0
    while ($n -gt 0) {
        $x = $x * 10
        $x += $n % 10
        $n = [int][math]::Floor($n / 10)
    }
    $x
}

```

Testing:

```
PS > rev(13457)
75431

PS > rev(rev(13457))
13457

```

# Answer
> 3 votes
# C++

```
#include<iostream>
#include<conio.h>
#include<fstream>
using namespace std;
int main()
{
    int i,size;
    float num;
    char ch;
    cout<<"enter the number \t: ";
    cin>>num;
    ofstream outf("tmp.tmp");
    outf<<num;
    outf.close();
    ifstream inf("tmp.tmp");
    inf.seekg(0,ios::end);
    size=inf.tellg();
    inf.seekg(-1,ios::cur);
    cout<<"Reverse of it\t\t: ";
    for(i=0;i<size;i++)
    {
        inf>>ch;
        if(ch!='0'||i!=0)
        cout<<ch;
        inf.seekg(-2,ios::cur);
    }
    inf.close();
            remove("tmp.tmp");
    getch();
    return 0;
}

```

### OUTPUT

Three sample runs

Test with zeros

It too **reverses floating numbers!!!**

If you want **to run this code** then run it on your computer because it creates a temporary file during its run-time and I am not sure if online compilers would make a temporary file on your computer

# Answer
> 2 votes
# ECMAScript 6

```
reverse=x=>{
    var k=-(l=(Math.log10(x)|0)),
        p=x=>Math.pow(10,x),
        s=x*p(l);
    for(;k;k++) s-=99*(x*p(k)|0)*p(l+k);
    return s
}

```

Then:

* `reverse(12345)` outputs `54321`
* `reverse(3240)` outputs `423`
* `reverse(6342975)` outputs `5792436`

# Answer
> 2 votes
# Fission

```
$SX/
\S?L
K\O

```

This program reverses the input.

```
$ echo -n '12345' | fsn tac.fsn
54321

```

# Answer
> 2 votes
# FORTH

I think this is the opposite of popular... but using Forth is always creative...

Let's create a new word

```
: REV
  BEGIN
    S->D 10 U/
    SWAP 1 .R
  DUP 0= UNTIL
CR ;

```

Here, it uses word U/ that returns remainder and quotient, remainder is sent to output as number within a field 1 character long, until dividend is zero. No string is used, at least until something is sent to video. I do not use a modulo operator, instead I use integer division with remainder and quotient. Let's try

```
12345 REV 54321
ok

```

# Answer
> 2 votes
# Turing Machine Code

Using the syntax from here.

```
0 * * l 0
0 _ # r 2
2 # # r 2
2 0 # l A
2 1 # l B
2 2 # l C
2 3 # l D
2 4 # l E
2 5 # l F
2 6 # l G
2 7 # l H
2 8 # l I
2 9 # l J
2 _ _ l Z
A * * l A
A _ 0 l Q
B * * l B
B _ 1 l Q
C * * l C
C _ 2 l Q
D * * l D
D _ 3 l Q
E * * l E
E _ 4 l Q
F * * l F
F _ 5 l Q
G * * l G
G _ 6 l Q
H * * l H
H _ 7 l Q
I * * l I
I _ 8 l Q
J * * l J
J _ 9 l Q
Q # # r 2
Q * * r Q
Z # _ l Z
Z * * l ZZ
ZZ _ * r ZZZ
ZZ * * l ZZ
ZZZ 0 _ r ZZZ
ZZZ * * * halt

```

Try it online!

# Answer
> 1 votes
# Python

```
import itertools

def rev(n):
    l = next(m for m in itertools.count() if n/10**m == 0)
    return sum((n-n/10**(i+1)*10**(i+1))/10**i*10**(l-i-1) for i in range(l))

```

# Answer
> 1 votes
# C

```
#include <stdio.h>

int c(int n) {
    return !n ? 0 : 1+c(n/10);
}

int p(int n) {
    return !n ? 1 : 10*p(n-1);
}

int r(int n) {
    return !n ? 0 : n%10*p(c(n/10))+r(n/10);
}

int main() {
    printf("%d\n", r(13457));

    return 0;
}

```

# Answer
> 1 votes
## Batch

Missed the part about not using strings - oh well.

```
@echo off
setLocal enableDelayedExpansion enableExtensions
for /f %%a in ('copy /Z "%~dpf0" nul') do set "ASCII_13=%%a"
set num=%~1
set cnum=%num%
set len=0
:c
if defined num set num=%num:~1%&set /a len+=1&goto :c
set /a len-=1
for /L %%a in (%len%,-1,0) do set /p "=!ASCII_13!!cnum:~%%a,1!"<nul

```

# Answer
> 1 votes
**Python 2**

```
import math

def reverseNumber(num):
    length = int(math.ceil(math.log10(num)))
    reversed = 0

    for i in range(0, length):
        temp = num // math.pow(10, length - i - 1)
        num -= temp * math.pow(10, length - i - 1)
        reversed += int(temp * math.pow(10, i))

    return reversed

print reverseNumber(12345)

```

# Answer
> 1 votes
## C#

```
private static int ReverseNumber(int forwardNumber)
{

    double forwardPower = 20;   //some number longer than Int32.MaxValue.Length
    double reversePower = 0;
    int reverseNumber=0;
    bool realNumberStarted=false;

    do
    {
        var tempInt= (int)(forwardNumber / Math.Pow(10, forwardPower));
        tempInt = (int)((((decimal)tempInt / 10) - (tempInt / 10))*10);
        if (tempInt>0 && !realNumberStarted)
        {
            realNumberStarted = true;
        }
        reverseNumber = reverseNumber+ tempInt * (int)Math.Pow(10, reversePower);
        if (realNumberStarted)
        {
            reversePower++;
        }

        forwardPower--;
    } while (forwardPower >=0);

    return reverseNumber;
}

```

Outputs

```
Console.WriteLine( ReverseNumber(12345));
Console.WriteLine(ReverseNumber(67584930));

```

---

```
54321
3948576

```

# Answer
> 1 votes
# C

```
#include <stdio.h>
#include <stdint.h>

int main() {
    uint32_t n = 0;
    scanf("%u", &n);

    while (n) {
        uint64_t o = (uint64_t) n * 3435973837u;
        uint32_t r = o >> 35;
        putchar(n - r * 10 + '0');
        n = o >> 35;
    }

    return 0;
}

```

Convert division (with constant divisor) to multiplication. I used this page to generate the factor.

The resulting code doesn't use `/` or `%` operators. Only `>>`, `*`, `+`, `-` are used.

### References

# Answer
> 1 votes
# C

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

unsigned  next_p( unsigned p )
{
  unsigned  next =
    ( 8 & ((p << 1) & ((~p) << 2)) )     |
    ( 4 & (~p) )                         |
    ( 2 & ((p >> 2) | ((p >> 1) & p)) );

  return next;
}

unsigned  mAp( unsigned x, unsigned p )
{
  unsigned  the_rest = 0;

  if (x > 1)
    the_rest = mAp( x >> 1, next_p(p) );

  if (x & 1)
    return (the_rest < 10 - p) ? the_rest + p : the_rest + p - 10;
  else if (x)
    return  the_rest;
  else
    return 0;
}

unsigned  fumA( unsigned x )
{
  unsigned  v = mAp( x >> 1, 2 );

  if (x & 1)
    ++v;

  if (v < 10)
    return v;

  return fumA( v-10 );
}

unsigned  rflipper(unsigned x, unsigned *p)
{
  unsigned  y = 0;

  if (x >= 10)
    y = rflipper( x / 10, p );

  y += fumA(x) * *p;

  (*p) *= 10;

  return y;
}

unsigned  rflip(unsigned x)
{
  unsigned  p = 1;

  return rflipper(x, &p);
}

int main(int argc, char*argv[])
{
  unsigned  i;

  if (argc < 2)
    {
      printf( "Useage:\n\t%s <positive integer>\n\n", argv[0] );
      return 0;
    }

  i = rflip(atoi(argv[1]));

  printf( "%d\n", i );

  return i;
}

```

# Answer
> 1 votes
# Extended BrainFuck

```
;;; variables
:input
:flag
:zero

;;; macros
;; read byte with all EOF conventions
;; + it also stops on linefeed
;; compatible BF interpreters translate CRLF => LF
;; so this would be portable
;; char value is one more than actual value
{read_byte
   $flag +
   $input ,
   +[-[10-[11+$flag-]]]
   >[@flag-$zero]
}

;; assumes current cell is empty
;; prints out a linefeed
{linefeed
   10+.
}

;; Assumes data starts to the left of current cell
;; prints until zero
{print_bytes_left
 <[.<]
}

;;; main program
while more $input +
( -
  >@input    ;; shift variables to the right
  &read_byte ;; read in byte
)
&print_bytes_left
&linefeed

```

Since someone beat me to a BF answer I rewrote it in EBF and made it portable and compatible. This doesn't wrap cells, it stops when encontering any one of the 3 EOF indicators or a linefeed. In compatible interpreters CRLF is translated to just a LF so this should work on any interpreter.

Usage:

```
% bf ebf.bf < rev.ebf > rev.bf
% echo 2345 | bf -w rev.bf
5432

```

The resulting BrainFuck code (output of `jitbf rev.bf --bf`) is:

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

```

Same as with the previous answer and the other BF entry this just stores the input and print it in reverse order.

I don't consider this an array since I made no way of random access (yes, I use arrays in (E)BF) so this is more a stack structure.

Strings do not exist in BF but we do store them in similar manner as in this code.

# Answer
> 1 votes
**C++**

```
 int main()
    {
    int num =123456;
    int rev =0;
    while(num)
    {
    rev = (rev *10) + (num%10);
    num = num /10;
    }
    cout << "Reverse :" << rev;
    return 0;
    }

```

# Answer
> 1 votes
This program accepts anything from input and outputs it reversed. So it can reverse strings, integers, floating point numbers, leading zero numbers, and other stuff. Please note that I'm not using **strings** but **chars**, so it should be ok.

# PHP, HTML

```
<?php
    while (false !== ($char = fgetc(STDIN))) {
    ?> <div style="float:right;"> <?= $char ?> </div> <?php
    }
?>

```

I don't know if `float:right` would be considered a string or not, and just in case, here's a longer solution without that.

# PHP, HTML, CSS

```
<style>
div {
    float:right;
}
</style>

<?php
    while (false !== ($char = fgetc(STDIN))) {
        ?> <div> <?= $char ?> </div> <?php
    }
?>

```

# Answer
> 1 votes
# PHP

No (built in) modulo, no string, no array;

```
function reverse ($n) {
    $r = 0;
    while ($n) {
        $r *= 10;
        $head = (int) ($n / 10);
        $r += $n - 10 * $head;
        $n = $head;
    }

    return $r;
}

```

# Answer
> 1 votes
# Golfscript

```
-1/

```

Pass an unsigned int as a command line arg

# Answer
> 1 votes
# C#

Using totally unnecessary recursion:

```
int Reverse(int i)
{
    return ReverseRecurse(i, 0);
}

int ReverseRecurse(int i, int r)
{
    if (i==0) return r;
    else
    {
        int d= i/10;
        return ReverseRecurse(d, (10*r)+(i-(d*10)));
    }
}

```

# Answer
> 1 votes
# Python

Probably not the best implementation, and I regret the need to import the math module, but here it is!

```
import math

def Reverse(n):
    revNum = 0
    digitsNum = math.floor(math.log10(n))

    for i in range(digitsNum, -1, -1):
        section = n // (10**(digitsNum-i))
        revNum += (section - 10*(section//10)) * 10**i

    return revNum

```

# Answer
> 1 votes
## Java

```
public class Reverser {

    public static long reverse(long x)
    {
        long n = (long) Math.floor(Math.log(x)/Math.log(10));
        long c = 0;
        for (long k=1; k<=n; k++)
        {
            c+= (long) (Math.floor( x * Math.pow(10, -1.0*k)) * Math.pow(10, n-k));
        }

        return (long) (x*Math.pow(10, n)) - (99 * c);

    }

    public static void main (String args[])
    {
        long a= 1230504;
        long b= reverse(a);
        System.out.println(String.format("a=%d, b=%d", a,b));
    }
}

```

# Answer
> 1 votes
```
function recurse(accumulator) {
    var power = accumulator.power;
    accumulator.power *= 10;
    if (accumulator.input >= accumulator.power)
         recurse(accumulator);
    while (accumulator.input >= power) {
        accumulator.input -= power;
        accumulator.result += accumulator.value;
    }
    accumulator.value *= 10;
 }

 function reverse(x) {
    var accumulator = { power: 1, value: 1, input: x, result: 0 };
    recurse(accumulator);
    return accumulator.result;
 }

```

# Answer
> 1 votes
# Java

This code has the following limitations:

1. it probably only works on the Eclipse console.
2. it's limited to natural integers.
3. it's artificially limited to a total of 100 figures (accross multiple calculations in sequence), this limit may be increased at the cost of performance, but the bottlenecks are probably the number of cores and the user's patience.
4. it's not thread-safe. Use at your own risk.

It essentially spawns a new Thread for each input byte and sleeps a bit less each time before writing it on the standard output.

```
public static void main(String[] args) {
    System.out.println("Enter the number you want to reverse.");
    int i = -1;
    int count = 0;
    while (true) {
        try {
            i = System.in.read();
            final int readEntry = i;
            if(readEntry!=13&&readEntry!=10){
                final int wait = count++;
                new Thread(new Runnable(){
                    @Override
                    public void run() {
                        try {
                            Thread.sleep(100-wait);
                        } catch (InterruptedException e) {
                            e.printStackTrace();
                        }
                        System.out.print(readEntry-48);
                    }
                }).start();
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

```

# Answer
> 1 votes
# **C#**

Magic numbers and shifting bits... no division, no modulo, no chars, no strings, no arrays. Just integers, adding, bit shifts, and multiplication.

```
    static void Main(string[] args)
    {
        UInt32 uin = UInt32.Parse(Console.ReadLine());
        UInt32 usave = uin;
        UInt64 rl;
        UInt32 q;
        UInt32 uout = 0;
        int digits = 0;
        while (uin > 0){
            rl = (UInt64)3435973837*uin;
            uin = (UInt32)(rl >> 35);
            digits++;
        }
        uin = usave;
        while (uin > 0)
        {
            rl = (UInt64)3435973837 * uin;
            q = (UInt32)(rl >> 35);
            uout += (uin - q * 10)*(UInt32)Math.Pow(10,(digits-1));
            uin = q;
            digits--;
        }
        Console.WriteLine(uout);
    }

```

This answer actually has some utility because, although it is highly obfuscated, it provides a really fast way to simultaneously implement `div 10` and `modulo 10` in 64-bit code. See : How do I implement an efficient 32 bit DivMod in 64 bit code

# Answer
> 0 votes
**Javascript**

```
function reverse(num) {
    for(var r = 0; num!=+[]; num = parseInt(num / 10, 10)) {
        r *= 10;
        r += num % 10;
    }
    return r;
}

```

# Answer
> 0 votes
# C++11

This code builds a function that prints an integer from STDIN in reverse, and then executes that function. Basically it is an example of really bad functional programming with loads of side effects.

```
#include <cstdio>
#include <functional>

void r(std::function<void()> f) {
    char c = getchar();
    c > 47 && c < 58
    ?   r([=]() {
            putchar(c);
            f();
        })
    :   f();
}

int main() {
    r([]() {
        putchar(10);
    });
    return 0;
}

```

# Answer
> 0 votes
# Java

```
int res = 0;
int numb = 25455236;
while(numb > 0){
  int temp = numb;
  int counter = 0;
  while (temp >= 0){
    temp = temp - 10;
    counter++;
  }
  res += 10-(counter*10-numb);
  res *= 10;
  numb = counter-1;
}
System.out.println(res/10);

```

# Answer
> 0 votes
**C**

No mod.

```
#include <stdio.h>
int main()
{
    unsigned long n, m=0;
    scanf("%lx", &n);
    while( n ) m = m<<4 | n&0xF, n >>= 4;
    printf("%lx\n", m);
}

```

# Answer
> 0 votes
## C

Here is an actual procedure that takes an unsigned as input and returns the reversed value.

```
unsigned long reverse(unsigned long n){
    unsigned long p=1, m=0, q=1;
    while( p<=n ) p *= 10;
    while( p /= 10 ){
        while( p<=n ) n -=p, m+= q;
        q *= 10;
    }
    return m;
}

```

# Answer
> 0 votes
## Dart

```
r(n, [a=0]) => n>0 ? r(n ~/ 10, a * 10 + n % 10) : a;

```

Use as:

```
main() { print(r(13457)); }  // prints 75431

```

Only works for non-negative integers.

---
Tags: popularity-contest
---


title: Substitution cipher

text:
# Question
Title: Substitution cipher
A substitution cipher is an encoding method where each letter in the alphabet is replaced with a fixed, different one; for example, given the following substitution map:

```
abcdefghijklmnopqrstuvwxyz
            ||
qwertyuiopasdfghjklzxcvbnm

```

The phrase "we all love cryptography" would be encoded as "vt qss sgct eknhzgukqhin".

The program will continuously read its input, one line at time; the first line will contain the substitution map, in the form of all 26 letters, in any order, without repetitions, missing letters or extraneous characters; it will be interpreted as "the first letter is the substitution for A, the second letter is the substitution for B \[...\] the 26th letter is the substitution for Z"; no output will be provided after reading it. For each subsequent line, the program will output the encoded text corresponding to the line. Only letters will be encoded; numbers, symbols and whitespaces will be simply copied to the output.

For simplicity, all input (including the substitution map) will only contain lowercase characters.

Sample input:

```
qwertyuiopasdfghjklzxcvbnm
hello
bye!
i don't know.

```

Sample output:

```
itssg
wnt!
o rgf'z afgv.

```

As usual, the shortest solution wins.

---

Additional clarifications on input:

* **The program must read its input stream** (I thought that was clear); command line parameters, files, named pipes, network sockets, quantum entanglement or extra sensorial perceptions are not allowed.
* **The input must include only the actual text to be processed**; quotes, brackets, commas or any other symbol, if found, should simply be copied to the output as they are.
* **No additional characters should be required in the input**. If your program requires the input text to be placed in quotes, brackets, commas or any other delimiter, then *You Are Doing It Wrong* (TM).
* "Line" is defined as a string of characters followed by a newline; the actual implementation of "newline" if usually left to the OS, but if you need to go into its details, just use whatever you prefer.
* An empty line is no special case; the program could either print an empty line or do nothing, but it should not print any actual text, crash, exit, destroy the operating system, set fire to the house, collapse the Sun in a black hole, summon demons from other planes of existence or replace your toothpaste with mayonnaise.
* There is no requirement for the program to run interactively; it's free to suck all its input in and then print all its output; there is also not any time limit on its execution, although it would be definitely preferable for it to terminate before the heat death of the universe.

# Answer
## Convex, ~~4~~ ~~6~~ 5 bytes

Crossed out 4 is still regular 4 :(

**Note: As @Dennis pointed out, the input format I was using was not up to spec. This version should comply with the new rules, though.**

```
lqT@Ë

```

Try it online

Explanation:

```
l       Read a line from input
 q      Read the rest of the input
  T     Push lowercase alphabet ("abcdefghijklmnopqrstuvwxyz")
   @    Rotate the top 3 items on the stack.
    er  Transliterate
        Implied output

```

Thanks to @LuisMendo for pointing out an error in the program
> 9 votes

# Answer
# Pyth, 7 bytes

```
V.zXNGz

```

Try it online!

How it works:

```
V.zXNGz
        G = "abcdefghijklmnopqrstuvwxyz"
        z = input()
V.z     for N in all_input():
   XNGz     N.translate(G,z)    <--- automatically printed

```
> 5 votes

# Answer
# JavaScript ES6, ~~65~~ ~~62~~ 49 bytes

Saved 2 bytes thanks to Neil.

```
(a,i)=>a.replace(/./g,x=>i[x.charCodeAt()-97]||x)

```

Takes an string of lines `a` and a dictionary `i`.
> 3 votes

# Answer
# CJam, ~~12~~ 8 bytes

*4 bytes saved thanks to Dennis!*

```
l_$q\@er

```

**Try it online!**

### Explanation

```
l        e# read a line
_$       e# fancy way to obtain string "abc...z". Thanks to Dennis!
q        e# read the rest of input as a string with newlines
\@       e# swap, rotate
er       e# transliterate. Implicit display

```
> 3 votes

# Answer
## sh + coreutils, 16 bytes

```
read s;tr a-z $s

```

15 bytes if input is from a terminal:

```
tr a-z `sed 1q`

```
> 3 votes

# Answer
# 05AB1E, 5 bytes

Code:

```
[A¹‡,

```

Explanation:

```
[      # Start an infinite loop.
 A     # Push the lowercase alphabet.
  ¹    # Push the first input (substitution map).
   ‡   # Transliterate. Since the arity of this function is 3 and there are only 2 values
                        on the stack, it implicitly takes a line of input.
    ,  # Pop and print.

```

So this continually reads a line of input and prints a line of input after. Uses **CP-1252** encoding. This is what I got with the console version:

```
D:\Golfing\05AB1E>C:\Python34\python.exe 05AB1E.py test.abe
qwertyuiopasdfghjklzxcvbnm
hello
itssg
welcome
vtsegdt
greetings, planet!
ukttzoful, hsqftz!

```

Trying this online might be a bit weird, since 05AB1E is trying to read another line of input, but there is none, so you need to kill it to receive output (doesn't work all the time). It *might* be a better idea to do this with the **console version** of 05AB1E. Try it online!.
> 3 votes

# Answer
# JavaScript 89

```
for(i=prompt,x=i(),n='';p=i();n+=p.replace(/./g,m=>x[m.charCodeAt(0)-97])+"\n");
alert(n)

```
> 2 votes

# Answer
# Ruby, ~~35~~ ~~31~~ 29 bytes

Credit to @QPaysTaxes for the `$_` trick, I had assumed that reading more from the STDIN object `$<` would change that variable, but it doesn't.

```
gets
$><<$<.read.tr('a-z',$_)

```

`String#tr` is basically a cipher substitution function, making things quite simple.
> 1 votes

# Answer
# MATL, 14 bytes

```
jXKx`jHY2KXEDT

```

The program exits with an error after producing the correct output (allowed by default).

**Try it online**
> 1 votes

# Answer
# Python 3, 50 bytes

```
lambda s,k:s.translate(dict(zip(range(97,122),k)))

```

Or if we really have to implement an infinite loop:

# Python 3, 70 bytes

```
t=dict(zip(range(97,122),input()))
while 1:print(input().translate(t))

```
> 0 votes

# Answer
# Pyth, ~~34 Bytes~~ ~~31 Bytes~~ ~~29 Bytes~~ 27 Bytes

Saved ~~3~~ ~~5~~ 7 bytes thanks to Kenny Lau

```
jmsm?&<JCk123>J96@hQ-J97kdt

```

Try it out!
> 0 votes

# Answer
# Factor, 155 bytes

The logic is actually pretty simple, it's just constraining to the REPL requirement that costs.

```
[let "abcdefghijklmnopqrstuvwxyz" readln string>array bi@ zip :> T [ t ] [ T readln string>array [ dup T key? [ T at ] [ ] if ] map "" join print ] while ]

```

Readable single-function version (don't ever write code like this):

```
:: monolithic-repl ( -- )
    "abcdefghijklmnopqrstuvwxyz" readln string>array bi@ zip
  :> table
  [ t ]
  [ table readln string>array
    [ dup table key?
      [ table at ] [ ] if
    ] map
    "" join print
  ] while ;

```

Readable, *Factored* version:

```
:: cipher-print ( cipher-table -- )
  readln string>array
  [ dup cipher-table key? [ cipher-table at ] [ ] if ] map
  "" join print ;

: cipher-get ( -- cipher )
  "abcdefghijklmnopqrstuvwxyz" readln
  string>array bi@ zip ;

:: cipher-repl ( -- )
  cipher-get :> table
  [ t ] [ table cipher-print ] while ;

```
> 0 votes

# Answer
## C++, 154 Bytes

```
#include <iostream.h>
#include "string.h"
using namespace std;

void encript_string() {
char en[26],in[1024];
string s=cin.getline();
strcpy(en,s.c_str());
while(1){
 s=cin.get_line();
 strcpy(in,s.c_str());
 int i=0,m=0;
 while(in[i] != 10) {
  m=in[i]-97;
  cout<<en[m];
 }
 cout<<"\n";
}
}

```
> 0 votes

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


title: Simulate Cookie Clicker

text:
# Question
Title: Simulate Cookie Clicker
# Intro

Cookie Clicker is a popular browser game in which the player has to click a cookie to gain... Cookies!
The player can buy upgrades which will automatically farm cookies for you. Sometimes a golden cookie will enter the screen, which will provide a bonus upon clicking it.

# Challenge

This challenge will not be about clicking a cookie. It will be about automating the cookie.
The player starts off with 0 cookies, and will gain cookies on every game tick. The goal of the challenge is to calculate the amount of ticks it takes to reach a certain amount of cookies.

# Input

Your program or function will have 2 input parameters.
The first parameter is the **goal**, which is simply the amount of cookies you need to finish.
The second parameter is a list of upgrades the player can buy. The format of the list will be explained in further detail in the paragraph **Upgrades - List format**.
For sake of convenience, you may assume that the input is always in the correct format. You don't have to deal with bad input.

# Output

Your program or function should *print or return* the amount of ticks it takes before the player has reached the goal amount of cookies.

# Upgrades

Every game-tick will earn the player some cookies. These are based on the upgrades of the player. If a player has no upgrades, the cookie production will be 1 cookie per tick. Once the player reaches enough cookies to buy an upgrade, he will automatically purchase it (before the next tick happens).
When the player has enough cookies after a tick to buy multiple upgrades, he will attempt to buy all possible upgrades, starting with the cheapest.

### List format

`[[100, '+', 1],[1000, '*', 2],[10000, '*', 10]`
This is an unordered list which contains 3 upgrades. The first parameter of an upgrade is the **price** of the upgrade. The second parameter is the **effect** of the upgrade and the third parameter is the **effect amount**.
The input list will contain no upgrades with the same price.
The only possible effects are `+` (addition) and `*` (multiplication).
`[100, '+', 1]` means that the cookie production will increase by 1 at a cost of 100 cookies.

# Golden cookies

Every 1000 ticks, the player will find a golden cookie. When this happens, the player will receive a bonus of 10% (rounded down) of his cookie amount. If the player has 1000 cookies at tick 1000, he will have 1100 cookies before tick 1001 happens.

# Order of events

After every tick a couple of actions can occur.

1. If the player has enough cookies, end the game
2. If the player has enough cookies, purchase upgrades
3. If the amount of ticks is a multiple of 1000; Golden cookie

# Example input + output

```
(0    , [])                              -> 0
(100  , [])                              -> 100
(1    , [[10, '+', 1]])                  -> 1
(10   , [[10, '+', 1]])                  -> 10
(1000 , [[100, '*', 2], [10, '+', 1]])   -> 310
(10000, [[10, '+', 1], [100, '*', 2]])   -> 2263

```

# Detailed example

```
(1000 , [[100, '*', 2], [10, '+', 1]])   -> 310

ticks: 8, cookies: 8, production: 1
ticks: 9, cookies: 9, production: 1
ticks: 10, cookies: 0, production: 2
ticks: 11, cookies: 2, production: 2
ticks: 58, cookies: 96, production: 2
ticks: 59, cookies: 98, production: 2
ticks: 60, cookies: 0, production: 4
ticks: 61, cookies: 4, production: 4
ticks: 70, cookies: 40, production: 4
ticks: 80, cookies: 80, production: 4
ticks: 260, cookies: 800, production: 4
ticks: 280, cookies: 880, production: 4
ticks: 300, cookies: 960, production: 4
ticks: 309, cookies: 996, production: 4
ticks: 310, cookies: 1000, production: 4 -- done

```

# Disclaimer

I will not be held responsible for any addictions caused by this challenge.

Happy golfing!

# Answer
> 2 votes
# Python2, 177 Bytes

```
def f(g,u):
 c=t=0;r=1
 while c<g:
    c+=r;t+=1
    if c>=g:break
    u=sorted(u)
    if u[0][0]<=c:
        h=u.pop(0);c-=h[0]
        exec('r'+h[1]+'=h[2]')
    if t%1000<1:c+=c//10
 return t

```

# Answer
> 1 votes
# CJam, 66

```
q~1$aa+$0{_W$<{{_2$0=0=<!}{\(~X@~:X;@\-}wT):T1e3%{_A/+}|X+}0?}h];T

```

Try it online

**Explanation:**

```
q~            read and evaluate the input (the goal and the array of upgrades)
1$aa+         append a dummy upgrade with the cost equal to the goal
               (to avoid the array becoming empty)
$             sort the upgrades lexicographically (so first by cost)
0             push 0, the initial number of cookies
{…}h          do-while loop, checking the last value as the condition
  _W$<        duplicate the number of cookies and check if it's smaller
               than the goal (at the bottom of the stack)
  {…}         if true… ("<condition><then part><else part>?" is an if statement)
    {…}       while… ("{condition}{block}w" is a while loop)
      _2$     duplicate the number of cookies and the array of upgrades
      0=0=    get the cost (first item) of the first upgrade
      <!      check if the number of cookies is not smaller than it
    {…}       do…
      \(      bring the array of upgrades to the top and take out the first upgrade
      ~       dump the price, effect (operator) and amount onto the stack
      X@      push X (cookie production) and bring the operator to the top
      ~:X;    evaluate the operator and store the result back in X
      @\-     subtract the price from the number of cookies
    w         (end) while
    T):T      increment T (the number of ticks, initially 0)
    1e3%      calculate T % 1000
    {…}|      if false (0) then…
      _A/+    add cookies/10 to the number of cookies (A=10)
    X+        add X (cookie production, initially 1) to the number of cookies
               to go to the next step
               since the result is not 0, the do-while loop continues
  0           else (if we reached the goal) push 0 to exit the loop
  ?           (end) if
];            pop everything left on the stack after the do-while loop
T             push T, the final number of ticks

```

# Answer
> 0 votes
## Lua, 220 Bytes

Can't think of a way to golf it down for the moment, it's still pretty long mostly because lua doesn't let you use loops carelessly regarding the bit count ^^'

```
function f(g,u)c=0t=0r=1while(c<g)do c=c+r t=t+1if(c>=g)then break end
for i=1,#u do x=u[i]if(c>=x[1])then c=c-x[1]r=x[2]=="+"and r+x[3]or r*x[3]table.remove(u,i)break
end end c=t%1000<1 and c+c/10or c end return t end

```

### Ungolfed

```
function f(g,u)
  c=0                       -- cookie counter
  t=0                       -- tick counter
  r=1                       -- cookie gain rate

  while(c<g)                -- iterate while cookie < goal
  do                        -- prevent returning 1 tick when the goal is 0
    c=c+r                   -- gain cookies
    t=t+1                   -- increment the tick counter
    if(c>=g)then break end  -- if we have enough cookies, exit
    for i=1,#u              -- iterate over the upgrades
    do
      x=u[i]                -- alias the current upgrade
      if(c>=x[1])           -- if we can, afford it
      then
        c=c-x[1]            -- deduce its price from our cookies
        r=x[2]=="+"         -- if it was an additive bonus
          and r+x[3]        -- add its value to the rate
          or r*x[3]         -- else multiply the rate by it
        table.remove(u,i)   --remove it from the list of upgrades
        break               -- exit the shop :D
      end
    end
    c=t%1000<1              -- every thousand ticks
      and c+c/10            -- get a golden cookie
      or c                  -- every other ticks does nothing
  end
  return t                  -- return the number of ticks it took
end

```

### Test Suite

You can copy paste the following code into this online compiler to run all the test cases.

```
function f(g,u)c=0t=0r=1while(c<g)do c=c+r t=t+1if(c>=g)then break end
for i=1,#u do x=u[i]if(c>=x[1])then c=c-x[1]r=x[2]=="+"and r+x[3]or r*x[3]table.remove(u,i)break
end end c=t%1000<1 and c+c/10or c end return t end
print(f(0,{}))
print(f(100,{}))
print(f(1,{{10,'+',1}}))
print(f(10,{{10,'+',1}}))
print(f(1000,{{10,'+',1},{100,'*',2}}))
print(f(10000,{{10,'+',1},{100,'*',2}}))

```

# Answer
> 0 votes
# Javascript ES6, 138 bytes

```
f=(g,s,p=1,c=-1,t=0)=>(c+=p)<g?f(g,s[b=0]?s.slice(b=(z=s.sort()[0])[0]<=c):s,b?eval(`p${z[1]}${z[2]}`):p,(b?c-z[0]:c)*(t%1e3?1:1.1),t+1):t

```

Ungolfed:

```
p = 1;  // production
c = -1; // cookies, -1 to account for the first tick
t = 0;  // ticks
f = function(g, s, p, c, t) { // goal, upgrades, production, cookies, ticks
    c += p;        // add production to cookies
    if (c < g) {   // cookies < goal
        b = 0;     // reset buy flag to false

        var upgradeArray;
        if (s[0]) { // our upgrade array isn't empty
            var sortedArray = s.sort();
            var upgrade = sortedArray[0];
            b = upgrade[0] <= c;       // price <= cookies
            upgradeArray = s.slice(b); // if we buy something, we remove the upgrade from the array because [1,2,3].slice(1) -> [2,3]
        } else {                       // our upgrade list is empty
            upgradeArray = s;
        }

        var newProduction;
        if (b) {    // we buy something
            newProduction = eval('p' + upgrade[1] + upgrade[2]) // evaluate p+10 for example
        } else {
            newProduction = p; // production is unchanged
        }

        var newCookies;
        if (b) {    // we buy something
            newCookies = c - upgrade[0]; // substract price from cookies
        } else {
            newCookies = c;
        }

        if (t % 1e3 == 0) {    // ticks % 1000 == 0
            newCookies *= 1.1; // golden cookie
        }

        return f(  // recursive call
            g,     // the goal doesn't change
            upgradeArray,
            newProduction,
            newCookies,
            t+1    // add a tick
        )
    } else {       // we have enough cookies, so we
        return t;  // return the amount of ticks
    }
}

```

Try it here

```
f=(g,s,p=1,c=-1,t=0)=>(c+=p)<g?f(g,s[b=0]?s.slice(b=(z=s.sort()[0])[0]<=c):s,b?eval(`p${z[1]}${z[2]}`):p,(b?c-z[0]:c)*(t%1e3?1:1.1),t+1):t

D.innerHTML= [
    f(0    , []),
    f(100  , []),
    f(1    , [[10, '+', 1]]),
    f(10   , [[10, '+', 1]]),
    f(1000 , [[100, '*', 2], [10, '+', 1]]),
    f(10000, [[10, '+', 1], [100, '*', 2]])
].join(`<br>`)
```

```
<div id=D>
```

---
Tags: code-golf
---


title: A Numpad's Knight Numbers

text:
# Question
Title: A Numpad's Knight Numbers
For the non-zero digits on a standard numpad

```
789
456
123

```

consider placing a chess knight at any digit and moving it around with any number of normal L-shaped jumps, tracing out a positive decimal integer. What positive integers can be expressed in such a way?

One of them is `38`, since the knight could start on the `3` and move left and up to the `8`. `381` and `383` are also possible.

`3` itself is possible if no jumps are taken (which is allowed). `5` is as well, but no other digits can be reached from the `5`, so it is the only number where the digit `5` appears.

Write a program or function that takes in a positive decimal integer (you may take it as a string if desired) and prints or returns a truthy value if the number can be expressed by a knight on a numpad in the way described, but otherwise outputs a falsy value.

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

## Examples

Truthy:

```
1, 2, 3, 4, 5, 6, 7, 8, 9, 16, 18, 38, 61, 81, 294, 349, 381, 383, 729, 767, 38183, 38383, 18349276, 183492761, 618349276

```

Falsy:

```
10, 11, 50, 53, 55, 65, 95, 100, 180, 182, 184, 185, 186, 187, 188, 189, 209, 305, 2009, 5030, 3838384, 4838383, 183492760

```

# Answer
# Jelly, ~~19~~ ~~15~~ 14 bytes

```
Doȷ’d3ạ2\P€=2P

```

Try it online! or verify all test cases.

### How it works

```
Doȷ’d3ạ2\P€=2P  Main link. Argument: n (integer)

D               Convert n to base 10 (digit array).
  ȷ             Yield 1000.
 o              Logical OR. This replaces each 0 with 1000.
   ’            Decrement each digit.
    d3          Divmod; replace each digit k with [k:3, k%3].
      ạ2\       Pairwise reduce by absolute difference.
                For each pair of adjacent digits [i, j], this computes
                [abs(i:3 - j:3), abs(i%3 - j%3)].
         P€     Compute the product of each result.
                n is a Numpad's Knight Number iff all products yield 2.
           =2   Compare each product with 2.
             P  Multiply the resulting Booleans.

```
> 16 votes

# Answer
## Python 2, 52 bytes

```
f=lambda n:n<6or`n%100`in'18349276167294381'*f(n/10)

```

Checks that any two consecutive digits are in the string `'18349276167294381'`. To get consecutive digits, rather than doing `zip(`n`,`n`[1:])`, the function repeatedly checks the last two digits and removes the last digit.
> 18 votes

# Answer
## Retina, ~~58~~ 40 bytes

Thanks to Sp3000 for suggesting this idea:

```
M&!`..
O%`.
A`16|18|27|29|34|38|49|67
^$

```

Try it online! (Slightly modified to run the entire test suite at once.)

Prints `1` for truthy and `0` for falsy results.

### Explanation

```
M&!`..

```

Find all overlapping matches of `..`, i.e. all consecutive pairs of digits, and join them with linefeeds.

```
O%`.

```

Sort the digits in each line, so that we only need to check half as many pairs.

```
A`16|18|27|29|34|38|49|67

```

Remove all lines which correspond to a valid move.

```
^$

```

Count the matches of this regex. That is, if all lines were removed, this matches the resulting empty string once, otherwise it fails to match and gives zero instead.
> 13 votes

# Answer
# Pyth - ~~35~~ 28 bytes

```
!s.bt/@c`C"_xÖ({Î¶z"2tsNYztz

```

Test Suite.
> 7 votes

# Answer
# Ruby, 57 bytes

Anonymous function. Argument is a string.

```
->n{(0..n.size).count{|i|!"16729438183492761"[n[i,2]]}<1}

```

Program with the test suite:

```
f=->n{(0..n.size).count{|i|!"16729438183492761"[n[i,2]]}<1}

a=%w{1 2 3 4 5 6 7 8 9 16 18 38 61 81 294 349 381 383 729 767 38183 38383 18349276 183492761 618349276
10 11 50 53 55 65 95 100 180 182 184 185 186 187 188 189 209 305 2009 5030 3838384 4838383 183492760}

a.each {|e|p [e, f[e]]}

```

I just encoded all the possible knight moves into a string and checked if every 2 digits within the input existed in that string.
> 7 votes

# Answer
# grep 58 bytes

```
grep "^((?=18|16|29|27|34|38|49|43|61|67|72|76|81|83|94|92).)*.$"

```

Because really, if you cannot beat grep...
> 6 votes

# Answer
## JavaScript (ES6), ~~65~~ 62 bytes

```
s=>[...s].every((c,i)=>!i|"16729438183492761".match(s[i-1]+c))

```

Returns true or false. I'd previously tried a recursive solution, which takes 63 bytes, and `map` and even `reduce` but they took me 73 bytes.

Edit: Saved 3 bytes thanks to @user81655.
> 6 votes

# Answer
## Haskell 46 bytes

```
q=zip<*>tail
all(`elem`q"16729438183492761").q

```

Usage example: `all(`elem`q"16729438183492761").q $ "183492761"` -\> `True`

How it works: It uses the lookup string found in @Kevin Lau's answer. `q` makes a list of pairs of adjacent chars from a string, e.g. `q "1672" -> [('1','6'),('6','7'),('7','2')]`. The function returns true if all pairs from the input appear in the pairs from the lookup string. `q` turns single digit inputs into the empty list, so `elem` always succeeds.
> 6 votes

# Answer
# C, ~~85~~ 81 bytes

Golfed:

```
i;f(char*b){i=*b++-49;return*b?(*b=="8749x7214"[i]||*b=="6983x1632"[i])&&f(b):1;}

```

Old non-recursive version (85 bytes):

```
i;f(char*b){for(;(i=*b++-49),*b&&*b=="8749x7214"[i]||*b=="6983x1632"[i];);return!*b;}

```

Old code with white-space and main program:

```
i;
f(char*b){
    for (; (i=*b++-49), *b     // i = index of digit + 1 in following arrays
        &&*b=="8749x7214"[i]   // 1st possible jump for 1..9
        ||*b=="6983x1632"[i];  // 2nd possible jump for 1..9
    );
    return !*b;
}

main(){
    char b[16];
    while(scanf("%s", b) == 1) printf("%d",f(b));
    return 0;
}

```

This accepts space-delimited numbers via standard input and outputs 0 if not-numpad-knight, or 1 otherwise.

The new 81-byte recursive version shaves 4 bytes.
> 6 votes

# Answer
# MATL, ~~38~~ ~~37~~ 29 bytes

This uses @QPaysTaxes idea.

```
I:8JK5:7Pvj!Uttnqh?)d|2:EQm}h

```

The output is a 2D, complex, non-empty array. It is truthy if all its values have nonzero real part, and falsy otherwise.

**Try it online!**
> 5 votes

# Answer
# 05AB1E, 29 bytes

Code:

```
"1Ôž±ÎqäÚ"•5(«U2÷¹¦2÷«vXyå})P

```

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

# Answer
# MATL, ~~25~~ ~~24~~ ~~33~~ 26 bytes

Shaved off 1 byte thanks to @LuisMendo!
@Dennis found a bug, and then fixed it! Thanks!

```
'bSVYXbTUZW'j47-)d2^48\1=A

```

Takes integer as input. Outputs 1/0.

Try it online!
> 4 votes

# Answer
# C, ~~140~~ 92 bytes

```
c;L(char*i){while(*i&&(!c||*i=="6743x1212"[c-49]||*i=="8989x7634"[c-49]))c=*i++;return !*i;}

```

*Assuming ASCII*

**Detailed** *Try it here*

```
// valid transition from x to n[x-'1'][0 or 1]

int n[9][2] =
{
    {'6','8'},{'7','9'},{'4','8'},
    {'3','9'},{'x','x'},{'1','7'},
    {'2','6'},{'1','3'},{'2','4'}
};

// i is a pointer to where to start on a string

bool L(char * i)
{
    char c = 0;

    // move if not \0 and (not-first-char or is a valid move)

    while((*i) && (!c || (*i)==n[c-'1'][0] || (*i)==n[c-'1'][1]))
    {
        c = (*i++);
    }

    return !(*i); // success if it's \0
}

```
> 4 votes

# Answer
## PowerShell v2+, ~~105~~ 96 bytes

```
param($a)((1..$a.length|%{'27618349294381672'.IndexOf($a[$_-1]+$a[$_])+1})-join'*'|iex)-or$a-eq5

```

Iterates through the input (which must be encapsulated with `""`) by verifying that the index of any sequential pair of characters is in the valid lookup string. I see Kevin Lau had something similar, but I came up with this independently. Each of those indices are added with `+1`, as the `.IndexOf()` function will return `-1` if the string isn't found. This will turn "not found"s into `0`.

We then `-join` all the resultant integer values with `*` and pipe that to `iex` (similar to `eval`). This will mean if any one of the indices is not found, the entire expression will result in `0`. That is encapsulated in parens and `-or`'d with `$a-eq5` for the special case of input `"5"` to achieve our resultant output.

### Test Runs

```
PS C:\Tools\Scripts\golfing> 1, 2, 3, 4, 5, 6, 7, 8, 9, 16, 18, 38, 61, 81, 294, 349, 381, 383, 729, 767, 38183, 38383, 18349276, 183492761, 618349276 | %{.\numpad-knight-numbers.ps1 "$_"}
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True

PS C:\Tools\Scripts\golfing> 10, 11, 50, 53, 55, 65, 95, 100, 180, 182, 184, 185, 186, 187, 188, 189, 209, 305, 2009, 5030, 3838384, 4838383, 183492760 | %{.\numpad-knight-numbers.ps1 "$_"}
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False

```
> 3 votes

# Answer
# Julia, ~~51~~ 49 bytes

```
n->diff(["@1634@8725"...][digits(n)+1]).^2%48⊆1

```

### Verification

```
julia> f=n->diff(["@1634@8725"...][digits(n)+1]).^2%48⊆1
(anonymous function)

julia> all(map(f,(1,2,3,4,5,6,7,8,9,16,18,38,61,81,294,349,381,383,729,767,38183,38383,18349276,183492761,618349276)))
true

julia> any(map(f,(10,11,50,53,55,65,95,100,180,182,184,185,186,187,188,189,209,305,2009,5030,3838384,4838383,183492760)))
false

```
> 3 votes

# Answer
## Actually, 30 bytes

```
;#pXZdX`Σ"67294381";'1+R+íu`Mπ

```

Takes input as a string. Outputs a positive integer for true and 0 for false.

Try it online!

Explanation:

```
;#pXZdX`Σ"67294381";'1+R+íu`Mπ
                                 (implicit) push input
;#pXZdx                         push zip(n[:-1], n[1;]) (pairs of digits)
       `Σ"67294381";'1+R+íu`M   map:
        Σ                         join digits
         "67294381";'1+R+         push "16729438183492761" (the magic string used in many other solutions)
                         íu       0-based index (-1 if not found), increment so 0 is not found and >=1 is the 1-based index
                             π  product

```
> 3 votes

# Answer
# C, ~~78~~ 85 bytes

```
char*a="9614397052";f(x){int b=x/10;return!b||b*x%5&&abs(a[x%10]-a[b%10])%6==1&f(b);}

```

Since everyone else has taken the input as a string, I tried doing it in integers. It works recursively from the least-significant digit (`a%10`); if it's the only digit, then return true. Otherwise, return true only if the tens digit (`b%10`) can't be reached from the units digit, and (recursively), the rest of the input satisfies the same test.

The test for reachability works by encoding the knight's tour linearly, and converting each digit to its position (zero to seven) on the tour. For digits `0` and `5`, we assign position nine, which is disconnected from the other positions. Then, mutually reachable numbers differ by one (mod eight); i.e. `a[x%10]-a[b%10]` is either ±1 or ±7. So we test the absolute difference (mod 6) against 1.

This solution works for any character encoding that is valid for C (i.e. digits have contiguous codes from 0 to 9).
> 2 votes

# Answer
# Java 8, ~~179~~ 167 Bytes

Places the number pad ints (minus 5 and 0) in a circle. `l` holds the circle index of these ints. If the difference of two indices is +/- 3 mod 8, then there is a knights move between the ints corresponding to those indices. Note that `x` is an `int[]`.

```
x->{if(x.length<2)return 1;int[] l={0,0,1,2,7,0,3,6,5,4};int o=l[x[1]];for(int i:x){int n=l[i];if(i%5==0||(Math.abs(n-o)!=3&&Math.abs(n-o)!=5))return 0;o=n;}return 1;}

```

**Update**

* **-11** \[16-12-10\] Switched to a lambda
* **-1** \[16-12-10\] Use `<2` instead of `==1`
> 1 votes

---
Tags: code-golf, number, grid, decision-problem, chess
---