title: Arbitrary Base Conversion

text:
# Question
Title: Arbitrary Base Conversion
Create a routine that takes an array of blocks in one numeric base system, and convert them to an array of blocks in another numeric base system. Both the from and to systems are arbitrary and should be accepted as a parameter. The input array can be an arbitrary length (If using a language where array lengths are not stored with the array, such as C, a length parameter should be passed to the function).

Here's how it should work:

```
fromArray = [1, 1]
fromBase = 256
toBase = 16
result = convertBase(fromArray, fromBase, toBase);

```

Which should return `[0, 1, 0, 1]` or possibly `[1, 0, 1]` (leading `0`s are optional since they don't change the value of the answer).

Here are some test vectors:

1. Identity Test Vector

```
fromArray = [1, 2, 3, 4]
fromBase = 16
toBase = 16
result = [1, 2, 3, 4]

```
2. Trivial Test Vector

```
fromArray = [1, 0]
fromBase = 10
toBase = 100
result = [10]

```
3. Big Test Vector

```
fromArray = [41, 15, 156, 123, 254, 156, 141, 2, 24]
fromBase = 256
toBase = 16
result = [2, 9, 0, 15, 9, 12, 7, 11, 15, 14, 9, 12, 8, 13, 0, 2, 1, 8]

```
4. Really Big Test Vector

```
fromArray = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
fromBase = 2
toBase = 10
result = [1, 2, 3, 7, 9, 4, 0, 0, 3, 9, 2, 8, 5, 3, 8, 0, 2, 7, 4, 8, 9, 9, 1, 2, 4, 2, 2, 3]

```
5. Non-even Base Vector

```
fromArray = [41, 42, 43]
fromBase = 256
toBase = 36
result = [1, 21, 29, 22, 3]

```

Other criteria / rules:

1. All integer variables should fit within a standard 32 bit signed integer for all sane input ranges.
2. You may convert to an intermediary representation, as long as the intermediary is nothing more than an array of 32 bit signed integers.
3. Expect to handle bases from 2 through 256. There isn't any need to support higher bases than that (but if you would like to, by all means).
4. Expect to handle input and output sizes **at least** up to 1000 elements. A solution that scales to 2^32-1 elements would be better, but 1000 is just fine.
5. This isn't necessarily about having the shortest code that will meet these rules. It's about having the cleanest and most elegant code.

Now, this isn't exactly trivial to do, so an answer that *almost* works might be accepted!

# Answer
# Python

```
# divides longnum src (in base src_base) by divisor
# returns a pair of (longnum dividend, remainder)
def divmod_long(src, src_base, divisor):
  dividend=[]
  remainder=0
  for d in src:
    (e, remainder) = divmod(d + remainder * src_base, divisor)
    if dividend or e: dividend += [e]
  return (dividend, remainder)

def convert(src, src_base, dst_base):
  result = []
  while src:
    (src, remainder) = divmod_long(src, src_base, dst_base)
    result = [remainder] + result
  return result

```
> 8 votes

# Answer
Here's a Haskell solution

```
import Data.List
import Control.Monad

type Numeral = (Int, [Int])

swap              ::  (a,b) -> (b,a)
swap (x,y)        =   (y,x)

unfoldl           ::  (b -> Maybe (b,a)) -> b -> [a]
unfoldl f         =   reverse . unfoldr (fmap swap . f)

normalize         ::  Numeral -> Numeral
normalize (r,ds)  =   (r, dropWhile (==0) ds)

divModLongInt            ::  Numeral -> Int -> (Numeral,Int)
divModLongInt (r,dd) dv  =   let  divDigit c d = swap ((c*r+d) `divMod` dv)
                                  (remainder, quotient) = mapAccumR divDigit 0 (reverse dd)
                             in   (normalize (r,reverse quotient), remainder)

changeRadixLongInt       ::  Numeral -> Int -> Numeral
changeRadixLongInt n r'  =   (r', unfoldl produceDigit n)
  where  produceDigit  (_,[])   =  Nothing
         produceDigit  x        =  Just (divModLongInt x r')

changeRadix :: [Int] -> Int -> Int -> [Int]
changeRadix digits origBase newBase = snd $ changeRadixLongInt (origBase,digits) newBase

doLine line = let [(digits,rest0)] = reads line
                  [(origBase,rest1)] = reads rest0
                  [(newBase,rest2)] = reads rest1
              in show $ changeRadix digits origBase newBase

main = interact (unlines . map doLine . lines)

```

And running the tests from the question:

```
$ ./a.out
[1,2,3,4] 16 16
[1,2,3,4]
[1,0] 10 100
[10]
[41, 15, 156, 123, 254, 156, 141, 2, 24] 256 16
[2,9,0,15,9,12,7,11,15,14,9,12,8,13,0,2,1,8]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 2 10
[1,2,3,7,9,4,0,0,3,9,2,8,5,3,8,0,2,7,4,8,9,9,1,2,4,2,2,3]
[41, 42, 43] 256 36
[1,21,29,22,3]

```
> 5 votes

# Answer
## R

Handles many thousands of elements* in less than a minute.

```
addb <- function(v1,v2,b) {
    ml <- max(length(v1),length(v2))
    v1 <- c(rep(0, ml-length(v1)),v1)
    v2 <- c(rep(0, ml-length(v2)),v2)
    v1 = v1 + v2
    resm = v1%%b
    resd = c(floor(v1/b),0)
    while (any(resd != 0)) {
        v1 = c(0,resm) + resd
        resm = v1%%b
        resd = c(floor(v1/b),0)
    }
    while (v1[1] == 0) v1 = v1[-1]
    return(v1)
}

redb <- function(v,b) {
    return (addb(v,0,b))
}

mm = rbind(1)

mulmat <- function(fromb, tob, n) {
    if (dim(mm)[2] >= n) return(mm)
    if (n == 1) return(1)
    newr = addb(mulmat(fromb,tob,n-1) %*% rep(fromb-1,n-1), 1, tob)
    newm = mulmat(fromb,tob,n-1)
    while (is.null(dim(newm)) || dim(newm)[1] < length(newr)) newm = rbind(0,newm)
    mm <<-  cbind(newr, newm)
    return(mm)
}

dothelocomotion <- function(fromBase, toBase, v) {
    mm  <<- rbind(1)
    return(redb(mulmat(fromBase, toBase, length(v)) %*% v, toBase))
}

```

* for \>500 elements you have to raise the default recursion level *or* do not reset the `mm` matrix on `dothelocomotion()`

Examples:

```
v1 = c(41, 15, 156, 123, 254, 156, 141, 2, 24)
dothelocomotion(256,16,v1)
2  9  0 15  9 12  7 11 15 14  9 12  8 13  0  2  1  8

dothelocomotion(256,36,c(41,42,43))
1 21 29 22  3

dothelocomotion(2,10, rep(1,90))
1 2 3 7 9 4 0 0 3 9 2 8 5 3 8 0 2 7 4 8 9 9 1 2 4 2 2 3

```
> 5 votes

# Answer
A less obfuscated and quicker JavaScript version:

```
function convert (number, src_base, dst_base)
{
    var res = [];
    var quotient;
    var remainder;

    while (number.length)
    {
        // divide successive powers of dst_base
        quotient = [];
        remainder = 0;
        var len = number.length;
        for (var i = 0 ; i != len ; i++)
        {
            var accumulator = number[i] + remainder * src_base;
            var digit = accumulator / dst_base | 0; // rounding faster than Math.floor
            remainder = accumulator % dst_base;
            if (quotient.length || digit) quotient.push(digit);
        }

        // the remainder of current division is the next rightmost digit
        res.unshift(remainder);

        // rinse and repeat with next power of dst_base
        number = quotient;
    }

    return res;
}

```

Computation time grows as o(number of digits2).
Not very efficient for large numbers.
Specialized versions line base64 encoding take advantage of base ratios to speed up the computations.
> 3 votes

# Answer
# Javascript

Thank you Keith Randall for your Python answer. I was struggling with the minutiae of my solution and ended up copying your logic. If anyone is awarding a vote to this solution because it works then please also give a vote to Keith's solution.

```
function convert(src,fb,tb){
  var res=[]
  while(src.length > 0){
    var a=(function(src){
      var d=[];var rem=0
      for each (var i in src){
        var c=i+rem*fb
        var e=Math.floor(c/tb)
        rem=c%tb
        d.length||e?d.push(e):0
      }
      return[d,rem]
    }).call(this,src)
    src=a[0]
    var rem=a[1]
    res.unshift(rem)
  }
  return res
}

```

### Tests

```
console.log(convert([1, 2, 3, 4], 16, 16))
console.log(convert([1, 0], 10, 100))
console.log(convert([41, 15, 156, 123, 254, 156, 141, 2, 24], 256, 16))
console.log(convert([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 2, 10))
console.log(convert([41, 42, 43], 256, 36))

/*
Produces:
[1, 2, 3, 4]
[10]
[2, 9, 0, 15, 9, 12, 7, 11, 15, 14, 9, 12, 8, 13, 0, 2, 1, 8]
[1, 2, 3, 7, 9, 4, 0, 0, 3, 9, 2, 8, 5, 3, 8, 0, 2, 7, 4, 8, 9, 9, 1, 2, 4, 2, 2, 3]
[1, 21, 29, 22, 3]
*/

```

This could probably be shrunk a lot, but I actually want to use it for a little side project. So I have kept it readable (somewhat) and tried to keep variables in check.
> 2 votes

# Answer
## Mathematica

No variables defined, any input accepted as long as it fits in memory.

```
f[i_, sb_, db_] := IntegerDigits[FromDigits[i, sb], db];

```

Test drive:

```
f[{1,2,3,4},16,16]
f[{1,0},10,100]
f[{41,15,156,123,254,156,141,2,24},256,16]
f[{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},2,10]
f[{41,42,43},256,36]

```

Out

```
{1,2,3,4}
{10}
{2,9,0,15,9,12,7,11,15,14,9,12,8,13,0,2,1,8}
{1,2,3 7,9,4,0,0,3,9,2,8,5,3,8,0,2,7,4,8,9,9,1,2,4,2,2,3}
{1,21,29,22,3}

```
> 2 votes

# Answer
### Scala:

```
def toDecimal (li: List[Int], base: Int) : BigInt = li match {
  case Nil => BigInt (0)
  case x :: xs => BigInt (x % base) + (BigInt (base) * toDecimal (xs, base)) }

def fromDecimal (dec: BigInt, base: Int) : List[Int] =
  if (dec==0L) Nil else (dec % base).toInt :: fromDecimal (dec/base, base)

def x2y (value: List[Int], from: Int, to: Int) =
  fromDecimal (toDecimal (value.reverse, from), to).reverse

```

Testcode with tests:

```
def test (li: List[Int], from: Int, to: Int, s: String) = {
 val erg= "" + x2y (li, from, to)
 if (! erg.equals (s))
   println ("2dec: " + toDecimal (li, from) + "\n\terg: " + erg + "\n\texp: " + s)
}

 test (List (1, 2, 3, 4), 16, 16, "List(1, 2, 3, 4)")
 test (List (1, 0), 10, 100, "List(10)")
 test (List (41, 15, 156, 123, 254, 156, 141, 2, 24), 256, 16, "List(2, 9, 0, 15, 9, 12, 7, 11, 15, 14, 9, 12, 8, 13, 0, 2, 1, 8)")
 test (List (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1),
   2, 10, "List(1, 2, 3, 7, 9, 4, 0, 0, 3, 9, 2, 8, 5, 3, 8, 0, 2, 7, 4, 8, 9, 9, 1, 2, 4, 2, 2, 3)")
 test (List (41, 42, 43), 256, 36, "List(1, 21, 29, 22, 3)")

```

Passed all tests.
> 1 votes

# Answer
# J, 109 105

Handles thousands of digits no sweat. *No integers harmed!*

```
e=:<.@%,.|~
t=:]`}.@.(0={.)@((e{:)~h=:+//.@)^:_
s=:[t[:+/;.0]*|.@>@(4 :'x((];~[t((*/e/)~>@{.)h)^:(<:#y))1')

```

### Examples

```
256 16 s 41 15 156 123 254 156 141 2 24
2 9 0 15 9 12 7 11 15 14 9 12 8 13 0 2 1 8

256 36 s 41 42 43
1 21 29 22 3

16 16 s 1 2 3 4
1 2 3 4

256 46 s ?.1000$45
14 0 4 23 42 7 11 30 37 10 28 44 ...

time'256 46 s ?.3000$45'  NB. Timing conversion of 3000-vector.
1.96s

```

It gets shorter.
> 1 votes

# Answer
# Smalltalk, 128

```
o:=[:n :b|n>b ifTrue:[(o value:n//b value:b),{n\\b}]ifFalse:[{n}]].
f:=[:a :f :t|o value:(a inject:0into:[:s :d|s*f+d])value:t].

```

tests:

```
f value:#[41 15 156 123 254 156 141 2 24]
  value:256
  value:16.
    -> #(2 9 0 15 9 12 7 11 15 14 9 12 8 13 0 2 1 8)

f value:#[1 2 3 4]
  value:16
  value:16.
    -> #(1 2 3 4)

f value:#[1 0]
  value:10
  value:100.
    -> #(10)

f value:#[1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]
  value:2
  value:10.
    -> #(1 2 3 7 9 4 0 0 3 9 2 8 5 3 8 0 2 7 4 8 9 9 1 2 4 2 2 3)

f value:#[41 42 43]
  value:256
  value:36.
    -> #(1 21 29 22 3)

```

and for your special amusement (**challenge: figure out, what's so special about the input value**):

```
f value:#[3 193 88 29 73 27 40 245 35 194 58 189 243 91 104 156 144 128 0 0 0 0]
  value:256
  value:1000.
    -> #(1 405 6 117 752 879 898 543 142 606 244 511 569 936 384 0 0 0)

```
> 0 votes

---
Tags: code-challenge, number
---


title: Run the Monty Hall Problem

text:
# Question
Title: Run the Monty Hall Problem
There’s already been a question about simulating the Monty Hall Problem. This one is different. The *user* will *play* the Monty Hall Problem. Your program will play the role of the host. Montybot, if you like.

Here are the steps:

1. Pick (randomly) which of the three doors hides the prize.
2. Output a visual display of three doors. A simple `ABC` will do. Or three squares. Or whatever.
3. Receive input choosing one of the doors. This could be a mouse click on the chosen door, or a single letter input (`B`) or whatever.
4. Open another door. You do not open the chosen door. You do not open the door hiding the main prize. That *may* mean you have no choice, or it *may* mean that you have a choice of two. If you have a choice of two, pick one at random. Visually indicate that the door has been opened and that no prize was hidden behind it. For a program text-based input/output, this could be as simple as outputting `AB0`, to show that door `C` has been opened. Feel free to be more inventive. If you’re doing a GUI program, your choice of display is up to you.
5. Accept input from the user. The user may input `stick` or `switch` (or, for a GUI program, click on buttons, or use a select input, or whatever). If the user enters anything other than `stick` or `switch`, the implementation is undefined. Do whatever you want.
6. Output the text `You won!` or `You lost`.
7. Terminate the progam.

Rules:

1. When you have to choose something *at random*, don’t worry about cryptographic randomness. Any `rand()` function will do.
2. The program must not cheat. The prize must be in place before the game starts. That is to say that the steps must be performed in the order given: *First* choose a door behind which to hide your prize, *then* ask the player to choose. The choice of which door to open in step 4 must happen in step 4: it is not selected in advance.
3. The output in step 6 must be honest.
4. This is code golf. Shortest code wins.

# Answer
# APL, 77

```
p←?3⋄d[e[?⍴e←(⍳3)~p,c←⍞⍳⍨⎕←d←3↑⎕A]]←'_'⋄⎕←d⋄⎕←'You','lost' 'won!'[(c=p)=5=⍴⍞]

```

Needs `⎕IO←0`. Tested on Dyalog.

**Explanation**

```
p←?3                       ⍝ p(rize) is a random number between 1 and 3
⎕←d←3↑⎕A                   ⍝ d(oors) is the string 'ABC'; output it
c←d⍳⍞                      ⍝ ask for one of the letters; c(hoice) is its position
o←e[?⍴e←(⍳3)~p,c]          ⍝ o(pen) is a random position except for p and c
d[o]←'_'                   ⍝ replace the o position in the d string with a '_'
⎕←d                        ⍝ output the modified d string
w←(c=p)=5=⍴⍞               ⍝ get choice, if it's stick (5 chars) and c=p, or neither, (w)in
⎕←'You','lost' 'won!'[w]   ⍝ print the result

```

**Examples**

```
      p←?3⋄d[e[?⍴e←(⍳3)~p,c←⍞⍳⍨⎕←d←3↑⎕A]]←'_'⋄⎕←d⋄⎕←'You','lost' 'won!'[(c=p)=5=⍴⍞]
ABC
A
AB_
stick
You lost
      p←?3⋄d[e[?⍴e←(⍳3)~p,c←⍞⍳⍨⎕←d←3↑⎕A]]←'_'⋄⎕←d⋄⎕←'You','lost' 'won!'[(c=p)=5=⍴⍞]
ABC
A
AB_
stick
You won!

```
> 2 votes

# Answer
## Python, 157

```
from random import*
C=choice
I=raw_input
p='\n> '
a='ABC'
g=C(a)
i=I(a+p)
print'You '+'lwoosnt!'[(i==g)^('w'in I(a.replace(C(list(set(a)-{g,i})),'_')+p))::2]

```

Example:

```
$ python monty.py
ABC
> A
AB_
> switch
You won!

```
> 2 votes

# Answer
# PowerShell: 192 174

**Changes from original:**

> * **-8 Characters** Since the visual display of doors can be "whatever" I realized that I could save some characters (particularly, the apostrophes required to define strings) by using numbers instead of letters.
> * **-8 Characters** By specifically choosing single-digit, prime numbers to represent the doors I could use the shorter modulo operator instead of an actual comparison operator when I needed to match doors to figure out the host's possible choices or the player's door swap. (Briefly explained here.)
> * **-2 Characters** Swapping the win/loss responses in the final if/else statement allowed me to use the modulo trick there also.

**Golfed Code**

```
$w=($d=3,5,7)|random;357;$p=read-host;-join$d-replace($h=$d|?{$_%$w-and$_%$p}|random),0;if((read-host)-match'w'){$p=$d|?{$_%$p-and$_%$h}}if($p%$w){'You lost'}else{'You won!'}

```

**Un-Golfed Code With Comments**

```
# Set up an array of doors ($d), and choose one to be the winner ($w).
$w=($d=3,5,7)|random;

# Show doors.
357;

# Get input and save player's choice ($p).
$p=read-host;

# Join the doors into one string, replacing the host's choice ($h) with a zero, and display them again.
-join$d-replace
(
    # Host will randomly choose a door from those which are not evenly divisible by $w or $p.
    $h=$d|?{$_%$w-and$_%$p}|random
 ),0;

# Get input from player. If it contains a 'w', switch doors.
# While this is generally a sloppy way to distinguish 'switch' from 'stick', it is allowed by the rules.
# "If the user enters anything other than stick or switch, the implementation is undefined. Do whatever you want."
if((read-host)-match'w')
{
    # Player will switch doors to one which is not evenly divisible by the $h or the original $p.
    $p=$d|?{$_%$p-and$_%$h}
}

# Announce the result.
# If $p is not evenly divisible by $w, player has lost. Otherwise, they have won.
if($p%$w){'You lost'}else{'You won!'}

# Variables cleanup - not included in golfed code.
rv w,d,p,h

```
> 2 votes

# Answer
## Javascript, 221 197

```
(function(q,r,s,t,u,v){f='ABC';d=[0,1,2];b=q()%3;a=r(f);d.splice(a,1);(a==b)?(r(f[d[q()%2]])==t)?s(u):s(v):(r(f[d[(d[0]==b)+0]])!=t)?s(u):s(v)})(Date.now,prompt,alert,'stick','You won!','You lost')

```

It uses two calls to Date.now() for randomness with a prompt in between to guarantee a delay. The user input is a 0-based index (the rule did say "whatever"). The following alert says which door was opened. Here's a slightly longer version that gives the answer before the user picks, to verify that it doesn't cheat:

```
(function(q,r,s,t,u,v){f='ABC';d=[0,1,2];b=q()%3;s('ans:'+b);a=r(f);d.splice(a,1);(a==b)?(r(f[d[q()%2]])==t)?s(u):s(v):(r(f[d[(d[0]==b)+0]])!=t)?s(u):s(v)})(Date.now,prompt,alert,'stick','You won!','You lost')

```

Fiddle: http://jsfiddle.net/acbabis/9J2kP/

**EDIT:** Thanks dave
> 0 votes

# Answer
# PHP \>= 5.4, 195 192

```
$r=[0,1,2];unset($r[$p=rand(0,2)]);$d='012';echo"$d\n";fscanf(STDIN,"%d",$c);unset($r[$c]);$d[array_rand($r)]='_';echo"$d\n",!fscanf(STDIN,"%s",$s),'You '.($s=='switch'^$c==$p?'won!':'lost.');

```

Output:

```
012
1
01_
stick
You won!

```
> 0 votes

---
Tags: code-golf
---


title: Hidden easter egg

text:
# Question
Title: Hidden easter egg
Here's a fun idea:

Write a simple game (tic-tac-toe, guess the number, etc) that has an easter egg in it, that can be triggered by a specific, special input from the user and does something cool, but the code for the game does not appear to contain any easter eggs (or any obviously obfuscated code) at first glance.

This is a popularity contest, so highest vote by the community wins.

# Answer
> 2 votes
## TI-BASIC

**Lock Screen** for your TI-84 calculator

```
:Repeat Str1="PASSWORD"
:Input Str1
:End

```

First one to find the egg gets a chicken ;)

---
Tags: popularity-contest, game, obfuscation
---


# Question
Title: Build a numerical library without using any primitive data type
The task is to build a numerical library for working with arbitrarily large integers that supports the following operations:

* addition
* subtraction
* multiplication
* division
* modulo operation

However, the library **must not use any primitive data types or arrays**, neither directly nor indirectly (including booleans). For example, if you use Java, you can neither use AtomicInteger (because it uses `bool` internally) nor HashMap (because it uses arrays internally). You'll need to create your own data structures, without using any primitive data types, to represent numbers. (Inherited methods such as Java's `hashCode` don't count, as long as you don't use them in any way.) The only exception is local use of booleans in order to use conditionals (see the clarification points below).

There is only one exception: In order to make your library actually testable, provide two functions to convert from and to native integer representation. For example:

```
int toNative(MyNum n) { ... }
MyNum fromNative(int n) { ... }

```

This is the only part of your code that can use built-in data types, and it must not do anything except the conversion.

If in doubt, please ask.

Criteria: The code should be elegant, *readable*, concise (but no code-golf, readability is more important than code size), well documented, and if possible, asymptotically efficient (provide and justify your functions asymptotic time and space complexity). The most up-voted answer in 10 days wins.

---

**Update:** Since the puzzle seemed impossible to many people, let me give **a hint**:

```
public abstract class Nat {
    public static Nat fromInt(int n) {
        Nat r = new Zero();
        for(int i = 0; i < n; i++)
            r = new Succ(r);
        return r;
    }

    public static int toInt(Nat n) {
        int i = 0;
        for(Nat m = n; m instanceof Succ; m = ((Succ)m).n)
            i++;
        return i;
    }
}

final class Zero extends Nat {
}

final class Succ extends Nat {
    public final Nat n;

    public Succ(Nat n) {
        this.n = n;
    }
}

```

This allows to represent any natural number without primitive types, even though not very efficiently.

To further clarify:

* Pointers are allowed to work with data structures as long as you use them only as opaque references. In particular, you may not use any pointer arithmetic.
* `NULL`/`null`s are allowed.
* If the language of your choice requires it, you can use booleans (or a similar data type) for conditionals, but only locally in functions/methods, not as fields in your data structures, and you can't use anything beyond boolean operations. Bonus if you manage it without booleans (many languages are capable of that, such as those that use pattern matching).
* Higher-level languages are better suited for the puzzle.

# Answer
> 8 votes
## Haskell

Haskell is pretty good at defining obvious things from scratch.
Almost all definitions are simple translations of math axioms.
Doesn't support negative numbers, behaves badly on errors (e.g. `1-2` or `1/0`).

```
data MyNum = Zero | S MyNum

toNative :: MyNum -> Integer
toNative Zero = 0
toNative (S n) = (toNative n) + 1
fromNative :: Integer -> MyNum
fromNative 0 = Zero
fromNative n = S $ fromNative $ n-1

-- numIfGE a b c = c if a>=b else 0
numIfGE _ Zero n = n
numIfGE Zero _ n = Zero
numIfGE (S a) (S b) n = numIfGE a b n

instance Num MyNum where
    a + Zero = a
    a + (S b) = S (a + b)

    a - Zero = a
    (S a) - (S b) = a - b

    a * Zero = Zero
    a * (S b) = a + (a*b)

a `divi` b = numIfGE a b (S $ (a - b) `divi` b)
a `modu` b = a - ((a `divi` b) * b)

```

# Answer
> 6 votes
### Python 3

The code is a basic lambda calculus implementation I did some time ago when learning about calculus using an online resource which I cannot find anymore (can anybody give me a hint).

It works fine for positive numbers - extension to negatives should be possible.

```
# booleans and if
TRUE    = lambda x: lambda y: x
FALSE   = lambda x: lambda y: y
IF      = lambda x: x

# numerals
ZERO    = lambda f: lambda x: x
IS_ZERO = lambda n: n(lambda x: FALSE)(TRUE)

INC     = lambda n: lambda f: lambda x: f(n(f)(x))
DEC     = lambda n: lambda f: lambda x: n(lambda g: lambda h: h(g(f)))(lambda y: x)(lambda y: y)

# combinators
Y       = lambda f: (lambda x: f(x(x)))(lambda x: f(x(x)))
Z       = lambda f: (lambda x: f(lambda y: x(x)(y)))(lambda x: f(lambda y: x(x)(y)))

# arithmetic
ADD     = lambda m: lambda n: n(INC)(m)
SUB     = lambda m: lambda n: n(DEC)(m)
MUL     = lambda m: lambda n: n(ADD(n))(ZERO)

IS_LEQ  = lambda m: lambda n: IS_ZERO(SUB(m)(n))
MOD     = Z(lambda f: lambda m: lambda n: IF(IS_LEQ(n)(m))(lambda x: f(SUB(m)(n))(n)(x))(m))
DIV     = Z(lambda f: lambda m: lambda n: IF(IS_LEQ(n)(m))(lambda x: INC(f(SUB(m)(n))(n))(x))(ZERO))

# conversion function
def toNative(n) : return n(lambda x: x+1)(0)
def fromNative(n) : return ZERO if n==0 else INC(fromNative(n-1))

# Test code
n13 = fromNative(13)
n5 = fromNative(5)

print("13/5 = ",toNative(DIV(n13)(n5)))
print("13%5 = ",toNative(MOD(n13)(n5)))

```

# Answer
> 3 votes
# Haskell

**unlimited range, negative and positive values, no booleans** except in native code

**O(n)** addition, subtraction (**asymptotically optimal**)
**O(n^2)** multiplication, division/modulo (no, I'm not going to implement the Karatsuba algorithm)

The representation is: a recursive type representing linked list of bits of the two's complement representation in the little endian order, terminated by either "all zeroes" or "all ones". Haskell has no trouble storing infinite lists in memory, but comparing their last elements is quite... hard.

`show` (producing a display form) runs backwards because prepending to a string is much faster than appending to it.

Addition, successor and predecessor are very simple. Carry is performed using the `succ`essor function. Note I didn't have to define subtraction. Haskell defines it for all `Num`bers as `a - b = a + negate b)`.

Multiplication is the classical binary lattice multiplication, with the sum step being performed bottom-up.

Division is the classical binary long division (trial subtraction).

Haskell defines two sets of integer division operations. `quot`ient/`rem`ainder round the quotient towards zero, while `div`ision/`mod`ulo round the quotient towards negative infinity. It defines `divMod` in terms of `quotRem` by subtracting one from the quotient (and the divisor from the modulus) if the sign of the remainder is opposite the sign of the divisor <sup>\[source\]</sup>. This is also the only place where the standard implementation uses native booleans internally (pattern matching probably does as well, but by the word of the author, this doeesn't count).

```
data LinkedInteger = Zero | MOne | And0 LinkedInteger | And1 LinkedInteger

toNative Zero = 0
toNative MOne = -1
toNative (And0 x) = 2 * toNative x
toNative (And1 x) = 2 * toNative x + 1

instance Show LinkedInteger where
   show = reverse.rshow
     where rshow  Zero    = "0.. "
           rshow  MOne    = "1.. "
           rshow (And0 x) = '0':(rshow x)
           rshow (And1 x) = '1':(rshow x)

fromNative   0  = Zero
fromNative (-1) = MOne
fromNative   x  | odd  x = And1 $ fromNative(x`div`2)
                | even x = And0 $ fromNative(x`div`2)

instance Enum LinkedInteger where
    succ Zero    = And1 Zero
    succ MOne    = Zero
    succ(And0 x) = And1 x
    succ(And1 x) = And0(succ x)

    pred Zero    = MOne
    pred MOne    = And0 MOne
    pred(And0 x) = And1(pred x)
    pred(And1 x) = And0 x

    toEnum = fromNative
    fromEnum = toNative

instance Num LinkedInteger where
    -- ensures sublinear performance in most cases
    Zero + x = x
    x + Zero = x
    MOne + x = pred x
    x + MOne = pred x
    And0 x + And0 y = And0 (x+y)
    And0 x + And1 y = And1 (x+y)
    And1 x + And0 y = And1 (x+y)
    And1 x + And1 y = And0 $ succ (x+y)

    negate  Zero    = Zero
    negate  MOne    = And1 Zero
    negate (And0 x) = And0 (negate x)
    negate (And1 x) = And1 $ pred (negate x)

    Zero   * y = Zero
    MOne   * y = -y
    And0 x * y =     And0 (x*y)
    And1 x * y = y + And0 (x*y)

    fromInteger = fromNative

    signum x = signum' (compare x Zero)
      where signum' LT = MOne
            signum' EQ = Zero
            signum' GT = And1 Zero

    abs x = ifNeg x (-x) x

mappend EQ y = y
mappend x  _ = x

instance Eq LinkedInteger where x == y = (compare x y) == EQ

instance Ord LinkedInteger where
    compare Zero Zero = EQ
    compare MOne MOne = EQ
    compare MOne Zero = LT
    compare Zero MOne = GT
    compare (And0 x) (And0 y) = compare x y
    compare (And1 x) (And1 y) = compare x y
    compare (And0 x) (And1 y) = mappend (compare x y) LT
    compare (And1 x) (And0 y) = mappend (compare x y) GT
    compare Zero x = compare (And0 Zero) x
    compare MOne x = compare (And1 MOne) x
    compare x Zero = compare x (And0 Zero)
    compare x MOne = compare x (And1 MOne)

ifLt w x y z = ifNeg' (compare w x) y z
  where ifNeg' LT y _ = y
        ifNeg'  _ _ z = z

ifNeg x = ifLt x 0

half  Zero    = Zero
half  MOne    = MOne
half (And0 x) = x
half (And1 x) = x

andBitFrom  Zero    = And0
andBitFrom  MOne    = And1
andBitFrom (And0 x) = And0
andBitFrom (And1 x) = And1

instance Real LinkedInteger where toRational = toNative

instance Integral LinkedInteger where
  quotRem _ Zero = undefined
  quotRem x y = (ifNeg x
                  (ifNeg y
                    (let n (q,r) = ( q, -r) in n(quotRem'(-x)(-y)))
                    (let n (q,r) = (-q, -r) in n(quotRem'(-x)  y )))
                  (ifNeg y
                    (let n (q,r) = (-q,  r) in n(quotRem'  x (-y)))
                                                (quotRem'  x   y ) ))

    where quotRem' Zero _ = (Zero, Zero)
          quotRem'    x y =
            let (qHalf, rHalf) = quotRem' (half x) y
                subdiv  = andBitFrom(x) rHalf
                subdiv' = subdiv - y
            in ifNeg subdiv' (And0 qHalf, subdiv) (And1 qHalf, subdiv')

  toInteger = toNative

```

# Answer
> 2 votes
## perl

Here's my take, in perl. I thought this was a code-golfing post at first, so you may see some vestiges of that in the code. Anyway, I went to some effort to make the code as "tight" as possible, probably a little tighter than I otherwise would have. But I didn't go too far over the deep-end. Also note that I left in the prototypes on public functions (despite them being considered bad practice), because it made the test cases much less tedious to code up.

As for time and space, I left notation of the runtimes in the source at the heading of each subroutine, but I didn't take the time to prove them or anything, just to convince myself. Space is the more serious consideration of course - this implementation uses O(n) space to store an integer n, which is pretty bad. I wasn't sure exactly what I could get away with in terms of chars or encoding counts in inheritance patterns and such so I figured I'd do it the "canonical" (if slower) way. This has other effects too, for example, it takes O(n+m) time to ask if n equals m.

All that said, here's nat.pm, a complete (I believe) implementation in perl:

```
#!/usr/bin/perl

use strict;
use warnings;

package nat;

sub prev() { $_[0]->{prev}; }
sub next() { $_[0]->{next}; }

sub zero() { bless { prev => undef, next => undef } }

sub inc($) {
  bless defined $_[0]->next ?
        { prev => undef, next => $_[0]->next->next } :
        { prev => $_[0], next => undef }
}
sub dec($) {
  bless defined $_[0]->prev ?
        { prev => $_[0]->prev->prev, next => undef } :
        { prev => undef, next => $_[0] }
}

sub is_zero($)     { !defined $_[0]->prev && !defined $_[0]->next };
sub is_negative($) { defined $_[0]->next };
sub is_positive($) { defined $_[0]->prev };

sub from_native($) {
  my ($n) = @_;
  my $x = zero;
  $n--, $x = inc($x) while $n > 0;
  $n++, $x = dec($x) while $n < 0;
  return $x;
}
sub to_native($) {
  my ($x) = @_;
  my $n = 0;
  --$n, $x = $x->next while defined $x->next;
  ++$n, $x = $x->prev while defined $x->prev;
  return $n;
}

# returns 1 if x has greater magnitude than y
# returns -1 if x has lesser magnitude than y
# returns 0 if x and y have the same magnitude
sub _equal_depth { # O(x+y)
  my ($x, $y, $c) = @_;
  while( defined $x->{$c} ) {
    return 1 if !defined $y->{$c};
    $x = $x->{$c};
    $y = $y->{$c};
  }
  return defined $y->{$c} ? -1 : 0;
}

# x<y => -1, x>y => 1, x==y => 0
sub spaceship($$) { # O(x+y)
  my ($x, $y) = @_;
  if( is_positive( $x ) ) {
    return is_positive( $y ) ? _equal_depth($x, $y, 'prev') : 1;
  } elsif( is_negative( $x ) ) {
    return is_negative( $y ) ? _equal_depth($y, $x, 'next') : -1;
  } else {
    return is_zero( $y ) ? 0 : is_positive( $y ) ? -1 : 1;
  }
}

# the below are all O(x+y) as a result of spaceship()
#sub is_lt($$)  { my ($x, $y) = @_; return spaceship($x, $y) == -1 }
#sub is_gt($$)  { my ($x, $y) = @_; return spaceship($x, $y) == 1 }
#sub is_le($$)  { my ($x, $y) = @_; return spaceship($x, $y) != 1 }
#sub is_ge($$)  { my ($x, $y) = @_; return spaceship($x, $y) != -1 }
sub equals($$) { my ($x, $y) = @_; return spaceship($x, $y) == 0 }

sub clone($) { # O(x)
  my ($x) = @_;
  my $r = zero;
  if( is_positive($x) ) {
    $x = $x->prev, $r = inc($r)  while  defined $x->prev;
  } elsif( is_negative($x) ) {
    $x = $x->next, $r = dec($r)  while  defined $x->next;
  }
  return $r;
}

sub _add_sub { # O(x+y)
  my $is_sub = pop;
  my ($x, $y) = map { clone($_) } @_;
  while( 1 ) {
    if( is_positive( $y ) ) {
      $y = dec( $y );
      $x = $is_sub ? dec( $x ) : inc( $x );
    } elsif( is_negative( $y ) ) {
      $y = inc( $y );
      $x = $is_sub ? inc( $x ) : dec( $x );
    } else {
      last;
    }
  }
  return $x;
}

sub add($$) { # O(x+y)
  return _add_sub(@_, 0);
}

sub minus($$) { # O(x+y)
  return _add_sub(@_, 1);
}

sub negate($) {
  my ($x) = @_;
  return minus( zero, $x );
}

sub magnitude($) {
  my ($x) = @_;
  return is_negative($x) ? negate($x) : $x;
}

sub mult($$) { # O(x*y)
  my ($x, $y) = map { clone($_) } @_;
  my $r = zero;
  $x = negate($x), $y = negate($y)  if  is_negative($y);
  while( !is_zero( $y ) ) {
    $r = add($r, $x);
    $y = dec( $y );
  }
  return $r;
}

sub _div { # O(x*y)
  my $is_mod = pop;
  my ($x, $y) = map { clone($_) } @_;
  die "tried to divide by zero" if is_zero( $y );
  if($is_mod && (is_negative($x) || is_negative($y))) {
    if('nat.t' ne (caller(1))[1]) {
      warn "warning: modular arithmetic with negative operands not well defined!\n";
    }
  }
  my $is_neg = ( is_negative($x) xor is_negative($y) );
  $x = magnitude($x);
  $y = magnitude($y);
  # count up from zero by one until we get to $x
  # whenever we get to a multiple, increment the result by one and zero the remainder
  my $q = zero;
  my $r = zero;
  while( !is_zero( $x ) ) {
    $r = inc( $r );
    if( equals( $y, $r ) ) {
      $r = zero;
      $q = inc( $q );
    }
    $x = dec( $x );
  }
  $r = negate($r), $q = negate($q)  if  $is_neg;
  return $is_mod ? $r : $q;
}

sub divi($$) {
  return _div(@_, 0);
}
sub mod($$) {
  return _div(@_, 1);
}

# export
no strict 'refs';
*{scalar(caller)."::$_"} = \&$_ for grep { !/^[A-Z_]/ } keys %nat::;

1;

```

... and here is the test script I used when building it:

```
#!/usr/bin/perl

use strict;
use warnings;

use Test::More;

use nat;

my $x;

my $zero = zero;
ok( $zero );
ok( 0 == to_native $zero );
ok( is_zero $zero );
ok( !is_negative $zero );
ok( !is_positive $zero );

my $pos1 = inc $zero;
ok( $pos1 );
ok( 1 == to_native $pos1 );
ok( 0 == to_native dec $pos1 );
ok( !is_zero $pos1 );
ok( !is_negative $pos1 );
ok( is_positive $pos1 );

my $neg1 = dec $zero;
ok( $neg1 );
ok( -1 == to_native $neg1 );
ok(  0 == to_native inc $neg1 );
ok( !is_zero $neg1 );
ok( is_negative $neg1 );
ok( !is_positive $neg1 );

my $pos2 = inc $pos1;
ok( $pos2 );
ok( 2 == to_native $pos2 );
ok( 3 == to_native inc $pos2 );
ok( 1 == to_native dec $pos2 );
ok( !is_zero $pos2 );
ok( !is_negative $pos2 );
ok( is_positive $pos2 );

my $neg3 = dec dec $neg1;
ok( $neg3 );
ok( -3 == to_native $neg3 );
ok( -2 == to_native inc $neg3 );
ok( -4 == to_native dec $neg3 );
ok( !is_zero $neg3 );
ok( is_negative $neg3 );
ok( !is_positive $neg3 );

# make sure inc/dec can go "across" zero
ok(  1 == to_native inc inc inc dec dec zero );
ok( -1 == to_native dec dec dec inc inc zero );

ok( equals $zero, $zero );
ok( !equals $zero, $pos1 );
ok( !equals $zero, $neg1 );
ok( !equals $pos1, $neg1 );

ok( !equals $pos1, $pos2 );
ok( equals $pos1, $pos1 );
ok( equals $pos2, $pos2 );

ok( !equals $neg1, $neg3 );
ok( equals $neg1, $neg1 );
ok( equals $neg3, $neg3 );

ok(  0 == spaceship $neg3, $neg3 );
ok(  0 == spaceship $neg3, $neg3 );
ok( -1 == spaceship $neg3, $neg1 );
ok(  1 == spaceship $neg1, $neg3 );
ok( -1 == spaceship $neg3, $zero );
ok(  1 == spaceship $zero, $neg3 );
ok( -1 == spaceship $neg3, $pos1 );
ok(  1 == spaceship $pos1, $neg3 );
ok( -1 == spaceship $neg3, $pos2 );
ok(  1 == spaceship $pos2, $neg3 );

ok(  0 == spaceship $neg1, $neg1 );
ok(  0 == spaceship $neg1, $neg1 );
ok( -1 == spaceship $neg1, $zero );
ok(  1 == spaceship $zero, $neg1 );
ok( -1 == spaceship $neg1, $pos1 );
ok(  1 == spaceship $pos1, $neg1 );
ok( -1 == spaceship $neg1, $pos2 );
ok(  1 == spaceship $pos2, $neg1 );

ok(  0 == spaceship $zero, $zero );
ok(  0 == spaceship $zero, $zero );
ok( -1 == spaceship $zero, $pos1 );
ok(  1 == spaceship $pos1, $zero );
ok( -1 == spaceship $zero, $pos2 );
ok(  1 == spaceship $pos2, $zero );

ok(  0 == spaceship $pos1, $pos1 );
ok(  0 == spaceship $pos1, $pos1 );
ok( -1 == spaceship $pos1, $pos2 );
ok(  1 == spaceship $pos2, $pos1 );

ok(  0 == spaceship $pos2, $pos2 );
ok(  0 == spaceship $pos2, $pos2 );

#ok( is_lt $neg3, $neg1 );
#ok( !is_lt $neg3, $neg3 );
#ok( is_le $neg3, $neg1 );
#ok( is_le $neg1, $neg1 );
#ok( !is_gt $neg3, $neg1 );
#ok( !is_gt $neg3, $neg3 );
#ok( !is_ge $neg3, $neg1 );
#ok( is_ge $neg1, $neg1 );

ok( equals( inc inc inc inc inc inc zero, from_native 6 ) );
ok( equals( dec dec dec dec dec dec dec zero, from_native -7 ) );

$x = clone $pos2;
ok( equals $pos2, $x );
ok( 2 == to_native $x );
$x = clone $neg3;
ok( equals $neg3, $x );
ok( -3 == to_native $x );

ok( 2 == to_native add $zero, $pos2 );
ok( 1 == to_native add $zero, $pos1 );
ok( 1 == to_native add $pos1, $zero );
ok( 2 == to_native add $pos1, $pos1 );
ok( 3 == to_native add $pos1, $pos2 );
ok( 3 == to_native add $pos2, $pos1 );
ok( 4 == to_native add $pos2, $pos2 );

ok( -3 == to_native add $zero, $neg3 );
ok( -1 == to_native add $zero, $neg1 );
ok( -1 == to_native add $neg1, $zero );
ok( -2 == to_native add $neg1, $neg1 );
ok( -4 == to_native add $neg1, $neg3 );
ok( -4 == to_native add $neg3, $neg1 );
ok( -6 == to_native add $neg3, $neg3 );

ok( -2 == to_native add $neg3, $pos1 );
ok( -1 == to_native add $neg3, $pos2 );
ok(  0 == to_native add $neg1, $pos1 );
ok(  1 == to_native add $neg1, $pos2 );

ok( -2 == to_native minus $neg3, $neg1 );
ok(  2 == to_native minus $neg1, $neg3 );
ok( -3 == to_native minus $neg3, $zero );
ok(  3 == to_native minus $zero, $neg3 );
ok( -4 == to_native minus $neg3, $pos1 );
ok(  4 == to_native minus $pos1, $neg3 );
ok( -5 == to_native minus $neg3, $pos2 );
ok(  5 == to_native minus $pos2, $neg3 );

ok( -1 == to_native minus $neg1, $zero );
ok(  1 == to_native minus $zero, $neg1 );
ok( -2 == to_native minus $neg1, $pos1 );
ok(  2 == to_native minus $pos1, $neg1 );
ok( -3 == to_native minus $neg1, $pos2 );
ok(  3 == to_native minus $pos2, $neg1 );

ok( -1 == to_native minus $zero, $pos1 );
ok(  1 == to_native minus $pos1, $zero );
ok( -2 == to_native minus $zero, $pos2 );
ok(  2 == to_native minus $pos2, $zero );

ok( -1 == to_native minus $pos1, $pos2 );
ok(  1 == to_native minus $pos2, $pos1 );

ok( equals $pos1, negate($neg1) );
ok( equals $neg1, negate($pos1) );
ok(  3 == to_native negate $neg3 );
ok(  1 == to_native negate $neg1 );
ok(  0 == to_native negate $zero );
ok( -1 == to_native negate $pos1 );
ok( -2 == to_native negate $pos2 );

ok( equals magnitude($pos1), magnitude($neg1) );
ok( equals magnitude($neg1), magnitude($pos1) );
ok( equals magnitude($pos1), $pos1 );
ok( equals magnitude($neg1), $pos1 );
ok( 3 == to_native magnitude $neg3 );
ok( 1 == to_native magnitude $neg1 );
ok( 0 == to_native magnitude $zero );
ok( 1 == to_native magnitude $pos1 );
ok( 2 == to_native magnitude $pos2 );

ok(  3 == to_native mult $neg3, $neg1 );
ok(  0 == to_native mult $neg3, $zero );
ok( -3 == to_native mult $neg3, $pos1 );
ok( -6 == to_native mult $neg3, $pos2 );

ok(  1 == to_native mult $neg1, $neg1 );
ok(  0 == to_native mult $neg1, $zero );
ok( -1 == to_native mult $neg1, $pos1 );
ok( -2 == to_native mult $neg1, $pos2 );

ok(  0 == to_native mult $zero, $zero );
ok(  0 == to_native mult $zero, $pos1 );
ok(  0 == to_native mult $zero, $pos2 );

ok(  1 == to_native mult $pos1, $pos1 );
ok(  2 == to_native mult $pos1, $pos2 );

ok(  4 == to_native mult $pos2, $pos2 );

ok(  3 == to_native divi $neg3, $neg1 );
ok(  0 == to_native divi $neg1, $neg3 );
eval { to_native divi $neg3, $zero }; ok($@);
ok(  0 == to_native divi $zero, $neg3 );
ok( -3 == to_native divi $neg3, $pos1 );
ok(  0 == to_native divi $pos1, $neg3 );
ok( -1 == to_native divi $neg3, $pos2 );
ok(  0 == to_native divi $pos2, $neg3 );

eval { to_native divi $neg1, $zero }; ok($@);
ok(  0 == to_native divi $zero, $neg1 );
ok( -1 == to_native divi $neg1, $pos1 );
ok( -1 == to_native divi $pos1, $neg1 );
ok(  0 == to_native divi $neg1, $pos2 );
ok( -2 == to_native divi $pos2, $neg1 );

ok(  0 == to_native divi $zero, $pos1 );
eval { to_native divi $pos1, $zero }; ok($@);
ok(  0 == to_native divi $zero, $pos2 );
eval { to_native divi $pos2, $zero }; ok($@);

ok(  0 == to_native divi $pos1, $pos2 );
ok(  2 == to_native divi $pos2, $pos1 );

ok( 0 == to_native divi from_native(0), from_native(3) );
ok( 0 == to_native mod  from_native(0), from_native(3) );
ok( 0 == to_native divi from_native(1), from_native(3) );
ok( 1 == to_native mod  from_native(1), from_native(3) );
ok( 0 == to_native divi from_native(2), from_native(3) );
ok( 2 == to_native mod  from_native(2), from_native(3) );
ok( 1 == to_native divi from_native(3), from_native(3) );
ok( 0 == to_native mod  from_native(3), from_native(3) );
ok( 1 == to_native divi from_native(4), from_native(3) );
ok( 1 == to_native mod  from_native(4), from_native(3) );
ok( 1 == to_native divi from_native(5), from_native(3) );
ok( 2 == to_native mod  from_native(5), from_native(3) );
ok( 2 == to_native divi from_native(6), from_native(3) );
ok( 0 == to_native mod  from_native(6), from_native(3) );
ok( 2 == to_native divi from_native(7), from_native(3) );
ok( 1 == to_native mod  from_native(7), from_native(3) );

ok(  0 == to_native divi from_native(-1), from_native(3) );
ok( -1 == to_native mod  from_native(-1), from_native(3) );
ok(  0 == to_native divi from_native(-2), from_native(3) );
ok( -2 == to_native mod  from_native(-2), from_native(3) );
ok( -1 == to_native divi from_native(-3), from_native(3) );
ok(  0 == to_native mod  from_native(-3), from_native(3) );
ok( -1 == to_native divi from_native(-4), from_native(3) );
ok( -1 == to_native mod  from_native(-4), from_native(3) );

done_testing();

```

# Answer
> 1 votes
# Go

Here's my partial submission in Go. Handles conversion to/from uint and sum to arbitrary precision.

The representation is binary, using a struct field (Unf) to store 1 bit of information (whether the pointer is nil or not) and another field (Chooie) to chain the next bit (more significant) which will chain another one if needed, and so on.

The performance is logarithmic with respect to the actual integers, just like in regular arbitrary precision libraries, except that the constant factors are hugely different.

```
package TerribleSecret

type Unf struct {
    Pak, Chooie *Unf
}

func FromNative(n uint) (u *Unf) {
    u = new(Unf)
    if n == 0 {
        return
    }
    if n&1 != 0 {
        u.Pak = u
    }
    u.Chooie = FromNative(n >> 1)
    return
}

func (u *Unf) ToNative() (n uint) {
    if u == nil {
        return
    }
    n = u.Chooie.ToNative()
    n <<= 1
    if u.Pak != nil {
        n |= 1
    }
    return
}

func (u *Unf) Add(n *Unf) {
    var f *Unf
    for {
        if u == nil {
            u = new(Unf)
        }
        if (n == nil || n.Pak == nil) != (f == nil) {
            if u.Pak != nil {
                u.Pak = nil
            } else {
                u.Pak = u
            }
        }
        if u.Pak != nil && (n == nil || n.Pak == nil) && f != nil {
            f = nil
        } else if u.Pak == nil && n != nil && n.Pak != nil && f == nil {
            f = n.Pak
        }
        if n != nil {
            n = n.Chooie
        }
        if n == nil && f == nil {
            break
        }
        if u.Chooie == nil {
            u.Chooie = new(Unf)
        }
        u = u.Chooie
    }
}

```

**Unit tests**

```
package TerribleSecret

import "testing"

func TestConversion(t *testing.T) {
    for n := uint(0); n < 10000; n++ {
        if r := FromNative(n).ToNative(); r != n {
            t.Fatalf("%d != %d", n, r)
        }
    }
}

func TestAdd(t *testing.T) {
    for x := uint(0); x < 1000; x++ {
        px := FromNative(x)
        for y := uint(0); y < 1000; y++ {
            py := FromNative(y)
            py.Add(px)
            if r := py.ToNative(); r != x+y {
                t.Fatalf("%d + %d = %d != %d", x, y, x+y, r)
            }
        }
    }
}

```

# Answer
> 1 votes
# C#

Supports the 5 operations and negative values.

```
using System;

namespace NonPrimitive
{
    enum ComparisonResult
    {
        Greater, Equal, Less, Error
    }
    class MainClass
    {
        static void Main ()
        {
            Leaf l1 = Leaf.FromInt (10);
            Leaf l2 = Leaf.FromInt (-20);
            Leaf l3 = Leaf.FromInt (30);
            Leaf l4 = Leaf.FromInt (40);
            Leaf l5 = Leaf.FromInt (50);
            Leaf l6 = Leaf.FromInt (60);
            Leaf l7 = Leaf.FromInt (-20);
            Leaf l8 = Leaf.FromInt (80);
            Leaf l9 = Leaf.FromInt (20);
            Leaf l0 = Leaf.FromInt (50);
            Leaf a = l1.Add (l2);
            Leaf s = l4.Subtract (l3);
            Leaf m = l6.Multiply (l5);
            Leaf d = l8.Divide (l7);
            Leaf mo = l0.Modulo (l9);
            Console.WriteLine ("10 + -20: {0}", a.ToInt ());
            Console.WriteLine ("40 - 30: {0}", s.ToInt ());
            Console.WriteLine ("60 x 50: {0}", m.ToInt ());
            Console.WriteLine ("80 / -20: {0}", d.ToInt ());
            Console.WriteLine ("50 % 20: {0}", mo.ToInt ());
        }
    }
    class Leaf
    {
        public Leaf Parent;
        public Leaf Child;
        public Leaf Negative;
        public Leaf (Leaf parent)
        {
            Parent = parent;
        }
        public Leaf ReverseSign()
        {
            Leaf k = this.GetGrandParent ();
            if(k.Negative != null)
                k.Negative = null;
            else
                k.Negative = new Leaf(null);
            return k;
        }
        public Leaf CreateNewLeaf()
        {
            Child = new Leaf(this);
            return Child;
        }
        public Leaf AttachLeaf(Leaf leaf)
        {
            Child = leaf;
            Child.Parent = this;
            return this;
        }
        public Leaf RemoveChild()
        {
            this.Child = null;
            return this;
        }
        public Leaf GetGrandChild ()
        {
            Leaf k = this;
            while(k.Child != null)
                k = k.Child;
            return k;
        }
        public Leaf Add (Leaf a)
        {
            Leaf t = this.GetGrandChild ().AttachLeaf (a.GetGrandParent ()).GetGrandChild ().Parent.RemoveChild ().GetGrandParent ();
            if ((a.Negative == null && this.Negative == null) ||
                (a.Negative != null && this.Negative != null))
                return t.GetGrandParent ();
            return t.GetGrandParent ().ReverseSign ();
        }
        public Leaf GetGrandParent ()
        {
            Leaf k = this;
            while(k.Parent != null)
                k = k.Parent;
            return k;
        }
        public Leaf Multiply (Leaf t)
        {
            Leaf ret = new Leaf(null);
            bool sign = (t.Negative == null && this.Negative == null) ||
                        (t.Negative != null && this.Negative != null);
            t = t.GetGrandParent ();
            Leaf temp = this;
            while (t.Child != null) {
                while(true)
                {
                    if(temp.Child == null)
                        break;
                    ret = ret.CreateNewLeaf ();
                    temp = temp.Child;
                }
                temp = this.GetGrandParent ();
                t = t.Child;
            }
            if(!sign)
                return ret.GetGrandParent ().ReverseSign ();
            return ret.GetGrandParent ();
        }
        public Leaf Divide (Leaf t)
        {
            Leaf temp = this.GetGrandParent ();
            bool sign = (t.Negative == null && this.Negative == null) ||
                        (t.Negative != null && this.Negative != null);
            Leaf ret = new Leaf (null);
            while (temp.Compare (t) == ComparisonResult.Greater || temp.Compare (t) == ComparisonResult.Equal) {
                temp = temp.Subtract (t);
                ret = ret.CreateNewLeaf ();
            }
            if(!sign)
                return ret.GetGrandParent ().ReverseSign ();
            return ret.GetGrandParent ();
        }
        public ComparisonResult Compare (Leaf a)
        {
            Leaf t = this.GetGrandParent ();
            a = a.GetGrandParent ();
            while (true) {
                if(t.Child == null && a.Child != null)
                    return ComparisonResult.Less;
                if(t.Child == null && a.Child == null)
                    return ComparisonResult.Equal;
                if(t.Child != null && a.Child == null)
                    return ComparisonResult.Greater;
                t = t.Child;
                a = a.Child;
            }
        }
        public Leaf Modulo(Leaf t)
        {
            Leaf temp = this.GetGrandParent ();
            bool sign = (t.Negative == null && this.Negative == null) ||
                        (t.Negative != null && this.Negative != null);
            while (temp.Compare (t) == ComparisonResult.Greater || temp.Compare (t) == ComparisonResult.Equal) {
                temp = temp.Subtract (t);
            }
            if(!sign)
                return temp.GetGrandParent ().ReverseSign ();
            return temp.GetGrandParent ();
        }
        public Leaf Subtract (Leaf a)
        {
            Leaf temp = this.GetGrandParent();
            a = a.GetGrandParent ();
            Leaf counter = new Leaf (null);
            while (true) {
                if(a.Child != null && temp.Child != null) {
                    temp = temp.Child;
                    a = a.Child;
                } else if (a.Child != null && temp.Child == null) {
                    a = a.Child;
                    counter = counter.CreateNewLeaf ();
                } else if (temp.Child != null && a.Child == null) {
                    temp = temp.Child;
                    counter = counter.CreateNewLeaf ();
                }
                else if(temp.Child == null && a.Child == null) {
                    break;
                }
            }
            a = a.GetGrandParent ();
            if(this.Compare (a) == ComparisonResult.Less)
                return counter.ReverseSign ();
            else
                return counter.GetGrandParent ();
        }
        public int ToInt()
        {
            Leaf temp = this.GetGrandParent ();
            int ret = 0;
            while(true)
            {
                if(temp.Child != null) {
                    ret++;
                    temp = temp.Child;
                    continue;
                }
                break;
            }
            if(this.Negative != null)
                return -ret;
            return ret;
        }
        public static Leaf FromInt (int a)
        {
            Leaf ret = new Leaf (null);
            bool neg = a < 0;
            if (neg)
                a = Math.Abs (a);
            for (int i = 0; i < a; i++) {
                ret = ret.CreateNewLeaf ();
            }
            while (true) {
                if(ret.Parent != null)
                    ret = ret.Parent;
                else
                    break;
            }
            if(neg)
                return ret.ReverseSign ();
            return ret;
        }
    }
}

```

Also, the class is named "Leaf" because it uses a tree-like structure.

# Answer
> 0 votes
## Brainfuck (incomplete)

Adding?

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

```

Subtracting?

```
,>,[-<->]

```

# Answer
> 0 votes
# C++ lambda functions

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

using std::function;

typedef function<int(int, function<int(int)>)> church;

church zero = [](int x, function<int(int)> f){ return x; };
function<church(church)> successor = [](church n)
{
  return [=](int x, function<int(int)> f)
  {
    return n(f(x),f);
  };
};

function<church(church, church)> plus = [](church n, church m)
{
  return [=](int x, function<int(int)> f)
  {
    return n(m(x, f), f);
  };
};

function<church(church, church)> times = [](church n, church m)
{
  return [=](int x, function<int(int)> f)
  {
    return m(x, [=](int y){ return n(y, f); });
  };
};

int main()
{
  function<int(int)> convert = [](int x){
    return x + 1;
  };
  auto resf0 = successor(successor(zero));
  int res0 = resf0(0, convert);
  printf("%i\n", res0); // 2

  auto resf1 = successor(resf0);
  int res1 = resf1(0, convert);
  printf("%i\n", res1); // 3

  auto resf2 = plus(resf0, resf1);
  int res2 = resf2(0, convert);
  printf("%i\n", res2); // 5

  auto resf3 = times(resf1, resf2);
  int res3 = resf3(0, convert);
  printf("%i\n", res3); // 15
}

```

This may not strictly follow the rules, but I wrote this, and somebody else revised it to this in August 2013. Ints are only used as a placeholder datatype, and also so that we can convert the weird function types to actual numbers.

---
Tags: popularity-contest, number, data-structures
---


title: Convert Regexes

text:
# Question
Title: Convert Regexes
Suppose you have existing regexes you wish to compile using one of the submissions to Compile Regexes.

In as few characters as possible, write a program that:

* accepts an existing regex as input, as either (a) one line from standard input; or (b) one argument from the command line; or (c) the contents of a textbox in a dialog box; then
* converts the regex into one that works with the compiler (see "Equivalent constructs"); then
* prints the new regex either (a) on standard output; or (b) in a dialog box.

## Equivalent constructs

You can convert...

* ... the anchors `^` and `$` to the empty string. If `^` is not at the beginning (and/or if `$` is not at the end), prepend (and/or append) `.*`. (You may assume any `^` anchor is the first character of the regex and any `$` anchor is the last character of the regex.)
* ... non-capturing groups to normal groups; replace `(?:x)` with `(x)`.
* ... character classes; replace `.` with `[0-9A-Za-z]`, `\d` with `[0-9]`, and `\D` with `[A-Za-z]`. No character class will occur inside a bracket expression.
* ... bracket expressions to groups containing alternation. For example, `[0-9A-FZ]` can become `(0|1|2|3|4|5|6|7|8|9|A|B|C|D|E|F|Z)`, and `[^0A-Za-z]` can become `(1|2|3|4|5|6|7|8|9)`.
* ... the plus operator: `+` to `{1,}`.
* ... braces (`x` is the nearest character or group to the left):

+ `x{m}` to m × `x`.
    + `x{m,}` to m × `x` followed by `x*`.
    + `x{m,n}` to m × `x` followed by either of:

    - (n-m) × `x?`
        - (n-m) × `(|x` then (n-m) × `)`
* ... the question mark operator: `x?` to `(|x)` or `(x|)`.

## Special rules

* You may assume all non-alphanumeric characters are metacharacters.
* Do not use general-purpose or Unicode algorithms to compress your code.
* Methods of input and output are implementation defined yet may not trivialize the solution.
* Using a special-purpose regex parsing library is prohibited. However, using one or more regexes as a tool for parsing the regex is OK (see below Scoring section).
* The input will never be longer than 1000 bytes.

## Scoring

Generally, the score is the number of characters in your submission. However, **you must double your score if you use a find-and-replace function and double it again if you use any regex or pattern matching function.** When writing your program, carefully consider whether to use regex and/or pattern matching functions, as using one just once quadruples your score.

## Test cases

Infinitely many valid outputs exist for each input case; thus, I have chosen a single example of possible output for each. The final test case is perhaps the trickiest.

### Begins with "A"

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

```
* Valid: Abra, Absol, Aerodactyl, Aipom, Alakazam
* Invalid: abra, absol, Bayleef, Beedrill

### Contains "sex"

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

```
* Valid: partsexpress, sextet, middlesex
* Invalid: partSEXpress, SEXtet, middleSEX

### Any decimal integer

```
 Input: ^\d+$
Output: (0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*

```
* Valid: 0, 7, 51, 370, 1040, 65536, 007, 051, 0000370, 001040, 065536
* Invalid: (the empty string), football, 10NIS

### Decimal integer without leading zeroes

```
 Input: ^(0|[1-9]\d*)$
Output: (0|(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)

```
* Valid: 0, 7, 51, 370, 1040, 65536
* Invalid: 007, 051, 0000370, 001040, 065536, football, 10NIS

### Lowercase Q without U word

```
 Input: ^[a-tv-z]*q[a-tv-z]*$
Output: (a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|v|w|x|y|z)*q(a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|v|w|x|y|z)*

```
* Valid: faqir, faqirs, qaid, qaids, qanat, qanats, qat, qats, qi, qindar, qindarka, qindars, qintar, qintars, qoph, qophs, qwerty, qwertys, sheqalim, sheqel, tranq, tranqs
* Invalid: Faqir, qAid, quid, liquefy

### Ends in a vowel then three or more consonants

```
 Input: [AEIOUaeiou][^0-9AEIOUaeiou]{3,}$
Output: (0|1|2|3|4|5|6|7|8|9|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z)*(A|E|I|O|U|a|e|i|o|u)(B|C|D|F|G|H|J|K|L|M|N|P|Q|R|S|T|V|W|X|Y|Z|b|c|d|f|g|h|j|k|l|m|n|p|q|r|s|t|v|w|x|y|z)(B|C|D|F|G|H|J|K|L|M|N|P|Q|R|S|T|V|W|X|Y|Z|b|c|d|f|g|h|j|k|l|m|n|p|q|r|s|t|v|w|x|y|z)(B|C|D|F|G|H|J|K|L|M|N|P|Q|R|S|T|V|W|X|Y|Z|b|c|d|f|g|h|j|k|l|m|n|p|q|r|s|t|v|w|x|y|z)(B|C|D|F|G|H|J|K|L|M|N|P|Q|R|S|T|V|W|X|Y|Z|b|c|d|f|g|h|j|k|l|m|n|p|q|r|s|t|v|w|x|y|z)*

```
* Valid: Bouncy, bouncy, erhythm
* Invalid: Noisy, noisy, Dodge, rhythm

### Exception to I before E, except after C

```
 Input: ^\D*([^Cc][Ee][Ii]|[Cc][Ii][Ee])\D*$
Output: (A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z)*((0|1|2|3|4|5|6|7|8|9|A|B|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z)(E|e)(I|i)|(C|c)(I|i)(E|e))(A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z)*

```
* Valid (and incorrectly spelled): AIRFEILD, AIRfeild, eyepeice, reciept, veiwer, zeitgiest
* Valid (yet correctly spelled): forfeit, glacier, science, zeitgeist
* Invalid (and correctly spelled): AIRFIELD, AIRfield, eyepiece, receipt, viewer
* Invalid (yet incorrectly spelled): 6AIRFIELD, AIRFIELD0, forfiet, glaceir, sceince, zietgiest

### U.S. amateur radio callsign

(Note that the FCC has reserved some of these (*e.g.* callsigns containing "SOS"), so not all of the matched callsigns could be legitimate callsigns used by U.S. amateur radio operators. 1x1 "special event" callsigns are not included.)

```
 Input: ^(?:[KNW]\d[A-Z]{2,3}|(?:A[A-L]|[KNW][A-Z])\d[A-Z]{1,2}|[KW][A-Z]\d[A-Z]{3})$
Output: ((K|N|W)(0|1|2|3|4|5|6|7|8|9)(A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z)(A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z)(|(A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z))|(A(A|B|C|D|E|F|G|H|I|J|K|L)|(K|N|W)(A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z))(0|1|2|3|4|5|6|7|8|9)(A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z)(|(A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z))|(K|W)(A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z)(0|1|2|3|4|5|6|7|8|9)(A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z)(A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z)(A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z))

```
* Valid: W1AW, AB0C, AB2MH, NZ9WA, K9DOG, KL5CD, KA2DOG, KN0WCW
* Invalid: WWVB, AB00, AM8ER, NZ99A, L9DOG, KNOWCW, KN0WCWW, kn0wcw

# Answer
# perl, 1111 916 bytes

There is more golfing to do, but under 1000 bytes seemed like a good stopping point, especially as no one else has answered this question yet =)

```
@l=("A".."Z","a".."z");@h=(0..9,@l);sub g{join"|",@_}sub p{length$_[0]>1&&substr($_[0],0,1)ne"("?"($_[0])":$_[0]}sub e{$e=$_[0];for(split//,$_[1]){return if$i[$e++]ne$_}1}sub x{push@o,$l=p g @_}$w=c("^.*\$");sub N{++$n}sub I{$i[$n]}sub c{@i=split//,shift;$f=$t=0;shift@i,$f=1 if$i[0]eq"^";pop@i,$t=1 if$i[-1]eq"\$";@o=();for($n=0;$n<@i;N){if(e$n,"(?:"){push@o,"(";N;N}elsif(e$n,"."){x@h}elsif(e$n,"\\d"){x 0..9;N}elsif(e$n,"\\D"){x@l;N}elsif(e$n,"["){N;my($v,@c);$v=1,N if"^"eq I;while(I ne"]"){push@c,$i[$n+1]eq"-"?I..$i[$n+=2]:I;N}@c=grep{$d=$_;!grep{$_ eq$d}@c}@h if$v;x @c}elsif(e$n,"?"){splice@o,-1,1,"(|$l)"}elsif(e$n,"+"){$l=p$l;splice@o,-1,1,"$l$l*"}elsif(e$n,"{"){N;my($j,$k,$h);$j.=$i[$n++]until","eq I||"}"eq I;if(","eq I){$h=1;$k.=I until$i[N]eq"}"}$l=p$l;@r=$l x$j;push@r,defined$k?"(|$l)"x($k-$j):"$l*"if$h;splice@o,-1,1,@r}else{x I}}push@o,$w if!$t;join"",$f?@o:($w,@o)}while(<>){chomp;print c($_).$/}

```

And here's a still-pretty-obfuscated, but at-least-it's-indented version:

```
use strict;
use warnings;

my @let = ('A'..'Z','a'..'z');
my @chars = (0..9,@let);

sub g { join('|',@_) }
sub p { length $_[0] > 1 && substr($_[0],0,1) ne '(' ? "($_[0])" : $_[0] };

sub comp {
  my @i = split//,shift;
  my ($front_anchor, $tail_anchor);
  if($i[0] eq '^') { shift @i; $front_anchor=1 }
  if($i[-1] eq '$') { pop @i; $tail_anchor=1 }
  my @out;
  my $last;
  for(my $n=0;$n<@i;++$n) {
    if($i[$n] eq '(' && $i[$n+1] eq '?' && $i[$n+2] eq ':') {
      push @out, '(';
      $n+=2;
    } elsif($i[$n] eq '.') {
      $last = g @chars;
      push @out, p $last;
    } elsif($i[$n] eq '\\' && $i[$n+1] eq 'd') {
      $last = g 0..9;
      push @out, p $last;
      ++$n;
    } elsif($i[$n] eq '\\' && $i[$n+1] eq 'D') {
      $last = g @let;
      push @out, p $last;
      ++$n;
    } elsif($i[$n] eq '[') {
      ++$n;
      my $invert=0;
      if($i[$n] eq '^') {
        $invert=1;
        ++$n;
      }
      my @c;
      do {
        if($i[$n+1] eq '-') {
          push @c, $i[$n]..$i[$n+2];
          $n+=2;
        } else {
          push @c, $i[$n];
        }
        ++$n;
      } while($i[$n] ne ']');
      @c = grep { my $c=$_; !grep { $_ eq $c } @c } @chars if $invert;
      $last = g @c;
      push @out, p $last;
    } elsif($i[$n] eq '?') {
      $last = "(|$last)";
      splice @out, -1, 1, $last;
    } elsif($i[$n] eq '+') {
      $last = p $last;
      $last = "$last$last*";
      splice @out, -1, 1, $last;
    } elsif($i[$n] eq '{') {
      ++$n;
      my ($bm, $bn, $hc);
      $bm .= $i[$n++] until $i[$n] eq ',' || $i[$n] eq '}';
      if($i[$n] eq ',') {
        $hc=1;
        $bn .= $i[$n] until $i[++$n] eq '}';
      }
      my @r;
      push @r, p $last for 1..$bm;
      push @r, p($last).'*' if $hc && !defined $bn;
      if($hc && defined $bn) {
        my $y = $bn - $bm;
        push @r, '(|'.p($last).')' for 1..$y;
      }
      splice @out, -1, 1, @r;
      undef $last; #no nested quantifiers
    } else {
      $last = $i[$n];
      push @out, $last;
    }
  }
  @out = (comp('^.*$'),@out) unless $front_anchor;
  @out = (@out,comp('^.*$')) unless $tail_anchor;
  return wantarray?@out:join"",@out;
}

while(<>) {
  chomp;
  print comp($_)."\n";
}

```
> 2 votes

---
Tags: code-golf, regular-expression, conversion
---


title: Doing shorter comparisons in PowerShell

text:
# Question
Title: Doing shorter comparisons in PowerShell
One of the annoying bits about PowerShell, which helps amplify its disadvantage against other languages in , is that there are no symbolic comparison or logical operators.

A comparison that could be as short as this:

```
$x<10&&$x>5

```

Has to be:

```
$x-lt10-and$x-gt5

```

This bloats the code for even the simplest of comparisons by about 50% compared to many other regular scripting and programming languages, never mind any golfing languages. Even an Excel formula for a similar comparison comes up shorter by one character!

```
=AND(A1<10,A1>5)

```

Another one that really bugs me:

```
$x==$k&&$i>9&&$i%10!=0

```

Has to be:

```
$x-eq$k-and$i-gt9-and$i%10-ne0

```

Interestingly, this one's *exactly* as long as the comparable formula for Excel, but that's mainly due to Excel's lack of a symbolic modulus operator.

```
=AND(A1=B1,C1>9,MOD(C1,10)<>0)

```

Is there a way this can be shortened at all, or is this strictly a limitation of the language? Are there any particular scenarios to keep in mind where shortcuts can be used for joining multiple comparisons?

# Answer
> 3 votes
I found a semi-edge case where a multiple comparison *can* be shortened. This is useful when you need to test two or more variables for equality, and only return true if all tests are true.

Instead of this:

```
$a-eq$b-and$c-eq$d

```

You might be able to do this:

```
"$a$c"-eq"$b$d"

```

It's worked for me in a Pisano Period script, where I changed:

```
$a-eq1-and$b-eq0

```

To:

```
"$a$b"-eq10

```

Another example:

```
$a-eq'apple'-and$b-eq'orange'

```

Can be cut down to:

```
"$a$b"-eq'appleorange'

```

# Answer
> 3 votes
You can also use the integer-to-boolean conversion trick mentioned by Danko to check prime numbers for inequality against other prime numbers. This could also work for composite numbers, provided that none of the numbers involved are evenly divisible by any of the others.

Example:

```
$x-ne$y-and$x-ne$z

```

Can be shortened to:

```
$x%$y-and$x%$z

```

Because non-zero integers are handled as `True` in PowerShell, any prime numbers will return `True` for `$x%$y` if they are different and `False` if they are the same.

# Answer
> 2 votes
Note that `[int]$x` is `0`(i.e. false) for all `$x` in the interval `[-0.5, 0.5]`, and `not 0`(i.e. true) for all `$x` outside of the interval (`[int]` rounds the number).

So, to check `$x -lt $m -or $x -lt $n` \- you can use the following:

```
[int]( $a * $x + $b )

```

where `$a = 1 / ( $n - $m )` and `$b = ( $m + $n ) / ( 2 * ( $m - $n ) )`

For example, to check that `$x` is not between `3` and `5`, you have `$a = 1 / 2` and `$b = -2` so:

```
[int]($x/2-2)

```

which is two characters shorter than

```
$x-lt3-or$x-gt5

```

To reverse the condition (i.e. to check that `$x` is between `3` and `5`), you could:

```
![int]($x/2-2)

```

which is still shorter than

```
$x-ge3-and$x-le5

```

It may not always be possible to get a short expression - it depends, of course, on what you get for `$a` and `$b`. However, if `$m = -$n` then `$b=0`, so the expression becomes rather trivial, e.g. to check that a number is between `-3` and `3` you can simply:

```
![int]($x/6)

```

---

Another possibility to consider is `"1"[$x]` which evaluates to `"1"` (i.e. true) if `$x` is rounded to `-1` or `0`, and "nothing" (i.e. false) otherwise. So, the expression will be true for all $x in the interval `(-1.5, 0.5]`. Note that `-1.5` is not included in the interval, as `[int]-1.5 = -2`.

With this method you can shorten an expression such as `$x -gt $m -and $x -le $n` into:

```
"1"[ $a * $x + $b ]

```

If you do the math as above, you get: `$a=-2/($m-$n)` and `$b=($m+3*$n)/(2*$m-2*$n)`.

So, for example:

```
$x-gt3-and$x-le5

```

becomes:

```
"1"[$x-4.5]

```

---
Tags: code-golf, tips, powershell
---


title: Reverse Regular expressions

text:
# Question
Title: Reverse Regular expressions
The idea here is to write a little segment that will spit out regular expression patterns when given a string that matches them.

As you might have guessed, this will be a popularity contest, and I'll accept whichever answer has the most upvotes by March 7th

pseudocode Example:

```
print(reverseRegex('dog'));
//prints /[a-z]{3}/, /dog/, and a bunch other stuff

```

EDIT: The regular expressions spat out should not exceed 3 times the input string's length

# Answer
> 1 votes
# Ruby

```
def esc chr
  '\\[]'.index(chr) ? "\\#{chr}" : chr
end

def reverse_regex str
  ords = str.chars.to_a.uniq.map(&:ord).sort
  prev = ords.first
  ranges = ords.slice_before{|x|
    prev, prev2 = x, prev
    prev2 + 1 != x
  }.map{|x| x[0]..x[-1]}

  reversed = "[#{ranges.map{|c|esc(c.min.chr) + (c.min == c.max ? '' : (c.min + 1 == c.max ? '' : '-') + esc(c.max.chr))}*''}]{#{str.size}}"
  reversed.size > str.size * 3 ? /#{Regexp.escape str}/ : /#{reversed}/
end

```

Sample outputs:

```
reverse_regex 'dogs are delicious'
  => /[ ac-egilorsu]{18}/
reverse_regex 'a'
  => /a/
reverse_regex ''
  => //
reverse_regex 'This is a test: []{}.*potato'
  => /[ *.:T\[\]aehiopst{}]{28}/

```

Now with ranges!

These regexen match the entire string (if you added `^...$` it would still match, but I'm too lazy to do that and add the required length check). Also, I'm assuming the `/`s don't count for length. (If they did, it would be impossible for input of empty string.)

# Answer
> 0 votes
# Python 3.2

If you wish for soemthing very short, as usual you can use `python`.

It is well known that you can do anything in `python` with few `import`s. In this case, this task is such simple that in `python 3.2` you don't even need an `include`.

```
def reverse_regex(string):
    return '/.*/'

print (reverse_regex('dog'))
print (reverse_regex('I can haz a cheezburger.'))
print (reverse_regex('123-ABC-abc'))

```

You will see all these expression are valid.

UPDATE:

This new code (although a bit more long) is able to show multiple regex for eacah word.

```
def reverse_regex(string):
    print ('/.*/')
    print ('/'+string+'/')

reverse_regex('dog')
reverse_regex('I can haz a cheezburger.')
reverse_regex('123-ABC-abc')

```

---
Tags: popularity-contest, regular-expression
---


title: Crossword Compulsions!

text:
# Question
Title: Crossword Compulsions!
Chris, a cryptic crosswords addict, has a set algorithm for the order in which he solves them.

We will use the above image as a guide.

1. Chris always starts off with the first across clue, in this case 1 Across. Chris is a capable crossword enthusiast, so it is assumed that he will always know the answer to the clue he is working on.
2. Once Chris completes a clue, he will check for all clues adjoining those he has completed (in the first case, 1 Down, 2 Down and 3 Down) and then complete the clue with the lowest number. If there are no adjoining clues, he would go to step 3.
3. If the clue is such that the next number (as described in Step 3) has both an across clue and a down clue, he will complete the across clue first (100% certainty, this borders on OCD!)
4. If there are no adjoining clues, he will go to the next available clue that's next in number (across or down)
5. Repeat from Step 2 until all clues are completed.

And this is where it comes down to you, dear coders. You have been tasked to create code that can, on being provided with a crossword template, provide output describing the order of clues based on Chris's algorithm for solving it.

The code will accept input of a crossword puzzle template, in the form of a `.` representing a white square and a `#` representing a black square.

**Example**:

```
.....#.........
.#.#.#.#.#.#.#.
...#...#.......
.#.#.#.#.#.#.#.
....#..........
##.#.#.#.#.#.#.
......#........
.###.#####.###.
........#......
.#.#.#.#.#.#.##
..........#....
.#.#.#.#.#.#.#.
.......#...#...
.#.#.#.#.#.#.#.
.........#.....

```

**Input** can be through: a) a file read of the representation of the crossword, or b) by line input of each line of the crossword, followed by `\n`, with a second `\n` indicating EOF.

And then it will determine the method by which Chris would solve it according to the above algorithm he has described.

**Output** must be in the format of a series of comma separated instructions in the form of `n(A|D)`, where `n` is the clue number followed by `A` for across or `D` for down.

So in the example above (both from the image, and the example template, which are the one and the same), the output would be:

`1A,1D,2D,3D,9A,10A,4D,5D,6D,7D,8D,11A,12A,13A,15A,14D,15D,16A,17A,18D,19D,20A,21D,23A,22D,24A,25D,27A,28A,26D,29A,30A,31A`

Shortest code wins...

**Testing**

You must provide with your submission the code, a byte count, as well as one of the four test cases represented in the `.` and `#` format, as well as the output generated from this input. There are four test cases, the three below as well as the above example template.

Example test cases:

Test Case 1

```
.....#
.#.#.#
...#..
.#.#.#
.....#
##.#..

```

Output: `1A,1D,2D,3D,4A,5A,6A,7A`

Test Case 2

```
.....#..
.#.##..#
.#....#.
...##.#.
.####...
......##

```

Output: `1A,1D,2D,5A,4D,4A,3D,3A,7A,8A,6D,9A`

Test Case 3

```
.........#
#.#.#.#.#.
....#...#.
#...#.#.#.
..###.#.#.
.#....#...
.#####...#
.....###..

```

Output: `1A,2D,3D,4D,5D,7A,8A,9A,10A,11A,11D,12A,13A,6D,14D,15A,16A,17A`

Test Case 4

```
.....#.........
.#.#.#.#.#.#.#.
...#...#.......
.#.#.#.#.#.#.#.
....#..........
##.#.#.#.#.#.#.
......#........
.###.#####.###.
........#......
.#.#.#.#.#.#.##
..........#....
.#.#.#.#.#.#.#.
.......#...#...
.#.#.#.#.#.#.#.
.........#.....

```

Output: `1A,1D,2D,3D,9A,10A,4D,4A,5D,6D,7D,8D,11A,12A,13A,15A,14D,15D,16A,17A,18D,19D,20A,21D,23A,22D,24A,25D,27A,28A,26D,29A,30A,31A`

Good luck!

# Answer
### GolfScript, 154 characters

```
:^,,{.^=46<{;-1}*)}%[.^n?)/zip[0]*]{1,%{,1>},}%:H"AD"1/]zip{~`{1$0=H{{0=}/}%.&$?)\+[\]}+/}%(2/\{0=)[\~\]}$+[]{1${1=1$&},.!{;1$1<}*1<:F~~@|@F-\1$}do;;]','*

```

Input has to be provided on STDIN. The examples yield the following results (check online):

```
1A,1D,2D,3D,4A,5A,6A,7A

1A,1D,2D,5A,4D,4A,3D,3A,7A,8A,6D,9A

1A,2D,3D,4D,5D,7A,8D,9A,10A,11A,11D,12A,13A,6D,14D,15A,16A,17A

1A,1D,2D,3D,9A,10A,4D,4A,5D,6D,7D,8D,11A,12A,13A,15A,14D,15D,16A,17A,18D,19D,20A,21D,23A,22D,24A,25D,27A,28A,26D,29A,30A,31A

```
> 6 votes

# Answer
# Mathematica ~~806~~ 477

(There appears to be a glitch in the ordering of the solution steps. I am looking into this.)

## Golfed

The function `q` finds the order of the crossword solutions.

```
i = Dimensions; v = MemberQ; u = Position; y = ToString; k = Select;
q@t_ :=
 (g@p_ := Characters@StringSplit[p, "\n"];
  w = g@t;
  a[{r_, c_}, z_] := (c != i[z][[2]]) \[And]
    v[u[z, "."], {r, c + 1}] \[And] ((c == 1) \[Or]
      v[u[z, "#"], {r, c - 1}]);
  b@z_ := k[u[z, "."], a[#, z] &];
  d[{r_, c_}, z_] := (r != i[z][[2]]) \[And]
    v[u[z, "."], {r + 1, c}] \[And] ((r == 1) \[Or]
      v[u[z, "#"], {r - 1, c}]);
  e@z_ := k[u[z, "."], d[#, z] &];
  Cases[Flatten[{
       If[v[b[w], #[[1]]], y[#[[2]]] <> "A"],
       If[v[e[w], #[[1]]], y[#[[2]]] <> "D"]} & /@ (MapIndexed[List,
        b[w] \[Union] e[w]] /. {{r_, c_}, {i_}} :> ({r, c} -> i))],
   Except[Null]])

```

---

## Ungolfed

```
q[t7_]:=
Module[{d,acrossSquareQ,acrossSquares,downSquareQ,downSquares,m,numberedCells},
(*w=g[t7];*)
g[p2_]:=Characters@StringSplit[p2,"\n"];
w=g[t7];
acrossSquareQ[{r_,c_},z_]:=(c!=Dimensions[z][[2]])\[And]MemberQ[Position[z,"."],{r,c+1}] \[And]((c==1)\[Or]MemberQ[Position[z,"#"],{r,c-1}]);
acrossSquares[z_]:=Select[Position[z,"."],acrossSquareQ[#,z]&];
downSquareQ[{r_,c_},z_]:=(r!=Dimensions[z][[2]])\[And]MemberQ[Position[z,"."],{r+1,c}] \[And]((r==1)\[Or]MemberQ[Position[z,"#"],{r-1,c}]);
downSquares[z_]:=Select[Position[z,"."],downSquareQ[#,z]&];
numberedCells[z_]:=acrossSquares[z]\[Union]downSquares[z];
m=MapIndexed[List,numberedCells[w]]/.{{r_?IntegerQ,c_?IntegerQ},{i_?IntegerQ}}:> ({r,c}-> i);
Cases[Flatten[{
If[MemberQ[acrossSquares[w],#[[1]]],ToString[#[[2]]]<>"A"],
If[MemberQ[downSquares[w],#[[1]]],ToString[#[[2]]]<>"D"]}&/@m],Except[Null]]]

```

---

`board` displays the crossword puzzle. The code is not included in the character count. Several sub functions from `q` are borrowed here.

```
board[p_]:=
Module[{q,g,w,downSquareQ,downSquares,acrossSquareQ,acrossSquares,numberedCells,m},
downSquareQ[{r_,c_},z_]:=(r!=Dimensions[z][[2]])\[And]MemberQ[Position[z,"."],{r+1,c}] \[And]((r==1)\[Or]MemberQ[Position[z,"#"],{r-1,c}]);
downSquares[z_]:=Select[Position[z,"."],downSquareQ[#,z]&];
acrossSquareQ[{r_,c_},z_]:=(c!=Dimensions[z][[2]])\[And]MemberQ[Position[z,"."],{r,c+1}] \[And]((c==1)\[Or]MemberQ[Position[z,"#"],{r,c-1}]);
acrossSquares[z_]:=Select[Position[z,"."],acrossSquareQ[#,z]&];
numberedCells[z_]:=acrossSquares[z]\[Union]downSquares[z];
g[p2_]:=Characters@StringSplit[p2,"\n"];
w=g[p];
m=MapIndexed[List,numberedCells[w]]/.{{r_?IntegerQ,c_?IntegerQ},{i_?IntegerQ}}:> ({r,c}-> i);
Grid[ReplacePart[w,m],Dividers->All,Background->{None,None,(#-> Black)&/@Position[w,"#"]}]]

```

---

## TestCases

**1**

```
t1=".....#
.#.#.#
...#..
.#.#.#
.....#
##.#..";
board[t1]
q[t1]

```

> {"1A", "1D", "2D", "3D", "4A", "5A", "6A", "7A"}

---

**2**

```
t2=".....#..
.#.##..#
.#....#.
...##.#.
.####...
......##";

board[t2]
q[t2]

```

> {"1A", "1D", "2D", "3A", "3D", "4A", "4D", "5A", "6D", "7A", "8A", "9A"}

---

**3**

```
t3=".........#
#.#.#.#.#.
....#...#.
#...#.#.#.
..###.#.#.
.#....#...
.#####...#
.....###..";

board[t3]

q[t3]

```

> {"1A", "2D", "3D", "4D", "5D", "6D", "7A", "8D", "9A", "10A", "11A", "11D", "12A", "13A", "14D", "15A", "16A", "17A"}

---

**4**

```
t4=".....#.........
.#.#.#.#.#.#.#.
...#...#.......
.#.#.#.#.#.#.#.
....#..........
##.#.#.#.#.#.#.
......#........
.###.#####.###.
........#......
.#.#.#.#.#.#.##
..........#....
.#.#.#.#.#.#.#.
.......#...#...
.#.#.#.#.#.#.#.
.........#.....";

board[t4]

q[t4]

```

> {"1A", "1D", "2D", "3D", "4A", "4D", "5D", "6D", "7D", "8D", "9A", "10A", "11A", "12A", "13A", "14D", "15A", "15D", "16A", "17A", "18D", "19D", "20A", "21D", "22D", "23A", "24A", "25D", "26D", "27A", "28A", "29A", "30A", "31A"}
> 3 votes

---
Tags: code-golf, crossword
---


# Question
Title: Align a horizontally-aligned, right-angled ASCII shape along a diagonal
Your program will receive an ascii shape consisting of only underscores `_`, pipes `|`, spaces  and newlines `\n`, which, together, represent a horizontally-aligned, right-angled shape. Together with this shape, on a new line, you will also receive either a positive or a negative integer, whose absolute value will be either one of `45`, `135`, `225` or `315` — signifying the degree that the original image should rotate. For instance:

```
 _
| |_
|___|
-45

```

Your program's job is to rotate this shape the provided amount of degrees. Following are the example outputs, for all possible degrees, given the above provided example shape:

1. for 45° or -315°:

```
 /\
/ /
\ \
 \/

```
2. for 135° or -225°:

```
 /\
/  \
\/\/

```
3. for 225° or -135°:

```
/\
\ \
/ /
\/

```
4. for 315° or -45°:

```
/\/\
\  /
 \/

```

Remember though: the original shape above is just an example. Your program should be able to handle any shape constructed with said characters (within reason, of course — let's say: with a maximum of 100 x 100 characters).

The output of your program should be the rotated image, constructed with forward slashes `/`, backward slashes `\`, spaces and newlines.

Shortest code, after one week, wins.

Note: although this challenge offers many similarities with these \[1\] \[2\] two challenges, I think this one offers just enough variation (because the original image is not supposed to be rotated at 90° angles) for it to generate interesting new results.

# Answer
# Python 2 - 285

```
import sys
l=list(sys.stdin)
L=len;R=range
r=L(l)-2
c=L(max(l,key=L))-2
k=r+c+1
d=int(l[-1])/90%4
a=d/2;x=a^d%2
z=1-x*2;t=1-a*2
m=[k*[' ']for i in R(k)]
for i in R(r+1):
 for j in R(L(l[i])-1):m[a*c+x*r+z*i+t*j][r-a*r+x*c-t*i+z*j]='  \/'[ord(l[i][j])/40^d%2]
for s in m:print''.join(s)

```

I strongly suspect it can be golfed more, tips are welcome.

Examples:

```
% python r45.py <<< "||
_____
45"
 /
\ /
 \
  \
   \
    \

% python r45.py <<< " _
| |_
|___|
-45"

    / \
 / \ /
    /
 \ /
  \

```

If the 2nd one looks misaligned, that's because of some issues with the question:
First, the underscore is at the bottom of the character "cell", while the pipe, slash and backslash are all in the middle. It would be fairer to use a dash (-) instead of underscore.
Second, with the rotation of the heart in the question, you couldn't represent it in any reasonable way if the first line was `___` (3 underscores) instead of `_`, as the 1st and 3rd underscore would be "capping" the pipes in the 2nd line.

Here's a better heart:

```
% python r45.py <<< " _
| |
|  _
|   |
 ___
-45"

 / \ / \

 \     /
  \   /
   \ /

```
> 3 votes

# Answer
# Mathematica \<225\> 27

## Second Version

Strange as it may seem, both the input and output are ASCII, "constructed with forward slashes /, backward slashes \\, spaces and newlines"!

The command works by `Rotate`ing the text within the Mathematica environment, while leaving the string in ASCII. The output is directly editable, as is, with no additional keystrokes or commands required. However, it will not export directly as ASCII. It can, however be exported directly as an image, as I have done here.

```
inputString =
 " _
  | |_
  |___|";

```

The following works by rotating the ASCII string on-screen.

```
s_~f~d_ := Rotate[s, -d Degree]

```

---

## Test Cases

```
f[s, 45]
f[s, -315]

```

---

```
f[s, 135]
f[s, -225]

```

---

```
f[s, -135]
f[s, 225]

```

##

```
f[s, 315]
f[s, -45]

```

---
> 2 votes

# Answer
**HTML/CSS/Javascript**

FIDDLE : http://jsfiddle.net/c5h2d/1/

```
<!DOCTYPE HTML>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Untitled Document</title>
<script type="text/javascript">
function rotate(){
    var x = document.querySelector("#i").value, y = document.querySelector("#t").value; document.querySelector("#a").innerHTML = y ;
    document.getElementById("a").style.transform = "rotate("+x+"deg)"

}
</script>

<style type="text/css">
#a{
    transform:rotate(45deg);
    position:absolute;
    top:50%;
    left:50%
}
</style>
</head>

<body>

<pre id="a"></pre>
<textarea id=t cols="30" rows="10"></textarea>
<input type="text" id=i /><button onclick='rotate()'>Rotate</button>
</body>
</html>

```
> 0 votes

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


# Question
Title: Code to display a string without calling any methods or functions
Write a code to display "I Love You". Without using any built-in tools or functions like `echo`, `System.out.println`, `printf`, ...

You are not allowed to directly call any function throughout the program execution, but the system environment or the compiler-generated code might do. This way, you can put your code in a `main` function or method that is called by the running environment, but your program should not further call any functions.

By the way, a function is not an instruction, nor a command nor an operator. So calling `sum(a, b)` is not valid, but making `a = b + c` is, even if the compiler reduces this to internal function calls.

This is a , so the valid answer with the most upvotes wins.

# Answer
## Html-asp- xhtml-tex-php.....

I didn't use any functions

```
I Love You

```
> 10 votes

# Answer
## Brainfuck

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

```

The heart looks horribly thin here, but it is a lot better on a text editor / terminal

Here's a nicely indented version:

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

```
> 10 votes

# Answer
# Javascript:

```
var l='I love you.';
if(window)window.status=l;
if(document)if(document.readyState=='complete')document.innerHTML=document.title=l;
else document.onload=function(){document.innerHTML=document.title=l;};
throw new l;

```

The part where it says 'function' is as ASSIGNMENT!

There is nothing in the question saying I can't assign functions and trigger events.

And the 'throw new l;' will say "I love you" in the error message.

This will show 'I love you' in the console, document, title and in the status bar.
> 6 votes

# Answer
# C

```
void main( )
{
  char *string="I Love You";
    volatile char *video = (volatile char*)0xB8000;
    while( *string != 0 )
    {
        *video++ = *string++;
        *video++;
    }
}

```
> 4 votes

# Answer
# Mathematica, GolfScript, Python Interpreter, bc

This outputs the sentence:

```
"I love you"

```
> 4 votes

# Answer
# PHP

Quite rule bending maybe...

```
<? ?>I Love You

```
> 2 votes

# Answer
# HTA - HyperText Application

```
I Love You

```

Microsoft says any plain text is valid HTA. They even mention in their official documentation that their "Hello, World." can be as simple as:

```
Hello, World.

```

Although most examples that you see on the web go the "official" route.
> 2 votes

# Answer
## Shell Script

```
mkdir "I Love You"
cd I\ Love\ You/
pwd | grep -o '/I Love You' | cut -c2-

```
> 1 votes

# Answer
# Smalltalk

as there is a read-eval-print-loop, and strings are self evaluating, this is trivial. From the command line, type this:

`stx -P "'I love you'`

A workspace, which is a basically a graphical wrapper for the `eval`, type in a string and select the "printIt" menu function.
> 1 votes

# Answer
# DOS Command Prompt

```
C:> prompt I Love You
I Love You

```
> 1 votes

---
Tags: popularity-contest
---


# Question
Title: Random number generation, without built-in random number generation libraries
**Task:**

Make a random number generator. The catch is that you can't use *any* built-in randomness functions. Your random numbers must be anything between 0 and 100, though they do not have to be floating point.

**Rules:**

* It must produce a pseudorandom number.
* Randomness defined: If you run it `x` times, then `x` times again, the two sequences will be unlikely to be identical. Where 2 \< x \< 10.
* It is **not** required that your random number generator passes any specific test about the quality of the generated numbers, as long as the previous rule is respected.
* Any language is accepted, except Golfscript, see here.
* This is , so the shortest answer in bytes wins.
* You may not hard-code the output numbers or read them from a file.
* Post 5 numbers generated by your program.
* Good luck!

# Answer
**C (46)**

The stack pointer is sort of a random number

```
main(x){printf("%d",((unsigned char)&x)%100);}

```

Numbers I got:

```
20
40
4
52
36

```
> 5 votes

# Answer
# python, 49

```
x=7
def r(x):print(x%100);return(69069*x+1)%2**32

```

This is my first time golfing, I think this is within the rules but I'm not sure. This is a simple linear congruential generator, with starting x value as seed. User time is not used. To use, type `x=r(x)`.

Here are the results:

```
7
84
25
62
47

```
> 4 votes

# Answer
# Linux utils and ALSA, 41

Not a winner, but possibly a more accurate source of random noise than the current time:

```
arecord -qfS32|od -l -j48 -N8|cut -c27-28

```

Sample 5 random numbers:

> 32 53 81 83 26
> 3 votes

# Answer
## Java - ~~250~~ 249 characters

```
import java.awt.*;class A{public static void main(String[]y)throws Exception{int z=200,u=z*z-1,n=7;java.awt.image.BufferedImage b=new Robot().createScreenCapture(new Rectangle(z,z));while(u>0)n^=b.getRGB(u/z,u--%z);System.out.println((n>>>1)%101);}}

```

It uses the topright 200x200 pixels of the screen as a source of randomness. The result is an integer between 0 and 100.

I runned it 5 times (this last version) and got this:

```
97
84
38
40
65

```

I had to move my windows around between each run.

Needless to say, it is a very poor random-generator:

* It is frequently predictable.
* It is easily stalled to keep giving always the same output.
* It is unlikely to produce each number between 0 and 100 with an equal probability.

So, this should not be used by any serious purpose.
> 2 votes

# Answer
# Python 2.7 - 82 bytes

```
import timeit
print timeit.Timer('for i in range(1000):i**i').timeit(1)*10000%100

```

This can definitely be golfed down more. I couldn't get `timeit` working when using `from timeit import*` but I think I only lost one character there. This is my first time using the module so I'm probably missing a lot of stuff that could save characters.

Times how long it takes in (seconds?) to calculate `i**i` for 0-999, multiplies that by 10000 and takes the modulus of 100 to get the result in the correct range.

Since this works off of hardware deviation rather than a pseudorandom formula like most programs do, you could even call this "more random" than `random.random()*100`. :)

(That last part probably isn't true, but until someone explains why I'll continue to believe it.)
> 1 votes

# Answer
## Java - 206 characters

```
class V{public static void main(String[]y)throws Exception{java.io.InputStream o=new java.net.URL("http://bit.ly/1gxstDI").openStream();int x,n=7;while((x=o.read())>0)n^=x;System.out.println((n>>>1)%101);}}

```

Similar to my previous answer. However, it is smaller and has some better randomness properties (but still bad). It fetches random data from http://en.wikipedia.org/wiki/Special:random as a seed (I am borrowing this idea from this answer).

Running it five times, here is the output:

```
25
15
93
32
9

```
> 1 votes

# Answer
# bash, 17

```
date +%N|tail -c3

```

Outputs the last two digits of a nanosecond timestamp.

### Sample output

```
$ ./random
24
$ ./random
52
$ ./random
82
$ ./random
69
$ ./random
72

```
> 1 votes

# Answer
# APL, 9 chars

```
101|+/⎕TS

```

Nothing new. It sums the components of the TimeStamp vector (current year, month… down to ms) and takes the remainder mod 101.
> 1 votes

# Answer
# bash — ~~108~~ 106 bytes

```
ls -al|tee -a X|grep -o [0-9]|xargs -n3|sed 's/ //g'|sort -u|awk 'BEGIN{X=0}{X=xor(X,$0)}END{print X%101}'

```

Gets a set of all three-digit triplets from a detailed listing, exclusive ORs them with each other, then prints a result modulus 101 to get \[0, 100\].

Depending on the activity in the directory, may be random-ish, or dynamic but predictable, but should never be static. Running it 1000 times, I was surprised that there didn't seem to be any patterns.

Sample output:

```
$ ls -al|tee -a X|grep -o [0-9]|xargs -n3|sed 's/ //g'|sort -u|awk 'BEGIN{X=0}{X=xor(X,$0)}END{print X%101}'
37
$ ls -al|tee -a X|grep -o [0-9]|xargs -n3|sed 's/ //g'|sort -u|awk 'BEGIN{X=0}{X=xor(X,$0)}END{print X%101}'
95
$ ls -al|tee -a X|grep -o [0-9]|xargs -n3|sed 's/ //g'|sort -u|awk 'BEGIN{X=0}{X=xor(X,$0)}END{print X%101}'
62
$ ls -al|tee -a X|grep -o [0-9]|xargs -n3|sed 's/ //g'|sort -u|awk 'BEGIN{X=0}{X=xor(X,$0)}END{print X%101}'
6
$ ls -al|tee -a X|grep -o [0-9]|xargs -n3|sed 's/ //g'|sort -u|awk 'BEGIN{X=0}{X=xor(X,$0)}END{print X%101}'
51

```
> 0 votes

# Answer
## Perl, 17

Seems like predictability isn't so much of an issue here, so here's a simple one:

```
print time**3%101

```

Five outputs:

```
59
38
17
14
94

```

I hope this answer highlights the importance of objectively defining the question.
> 0 votes

# Answer
**PowerShell (66)**

```
[Convert]::ToInt32((""+([guid]::newguid())).SubString(0,2),16)%100

```

5 outputs:

```
10
92
13
84
0

```
> 0 votes

# Answer
### Ruby, 69

```
def r()(Time.now.to_f.to_s+$$.to_s+$-I.join).bytes.reduce(:+)%100;end

```

Online Version for testing. Uses the current time in ms, the process id ($$) and the runtime environment ($-I) for creating a pseudo-random number.

Output:

```
47
44
39
43
88

```
> 0 votes

# Answer
## Java, 99 chars

```
class b{public static void main(String[]a){System.out.println(System.nanoTime()/a.hashCode()%99);}}

75
28
34
88
16

```

If you want to be really really cheap:

**java 88 Chars**

```
class b{public static void main(String[]a){System.out.println(System.nanoTime()/9%99);}}

99
86
61
15
19

```
> 0 votes

# Answer
# Smalltalk, 39

not a production quality random generator:

```
OperatingSystem getMicrosecondTime\\101

```

but as I generated those 5 values by eval'ing them interactively, it's me who makes it random.

Output of 5 evaluations:

```
 93 28 25 6 25

```

PS: the free running us timer is normally used for profiling...

A *much* better random gen would be:

```
'/dev/random' asFilename readStream nextByte/2.55

```
> 0 votes

# Answer
## CMD / Batch - 14 Bytes

```
echo %time:~9%

```

Grabs milliseconds off the end of the variable `%time%`.

Add `@` before the command to make it only output the number.

```
C:\>echo %time:~9%
40

C:\>echo %time:~9%
53

C:\>echo %time:~9%
19

C:\>echo %time:~9%
73

C:\>echo %time:~9%
25

```
> 0 votes

---
Tags: code-golf, number, random
---


title: maximum subarray variant

text:
# Question
Title: maximum subarray variant
**Problem** There is a circular track containing fuel pits at irregular intervals. The total amount of fuel available from all the pits together is just sufficient to travel round the track and finish where you started. Given the the circuit perimeter, list of each fuel pit location and the amount of fuel they contain, find the optimal start point on the track such that you never run out of fuel and complete circuit.

**Sample Input**

```
(location, fuel)

(0/100, 6)
(2,16)
(18,1)
(30,45)
(84,5)
(92,27)

```

circuit length - 100, total fuel-100

# Answer
**JavaScript 140 chars**

For the first solution, I assume that the fuel pits are provided in order order of location around the track and in the form:

```
var fuelPitInfo = [
    {
       location: 2,//The location from some point on the track
       fuelDistance: 1//The distance you can travel with the fuel from this stop
    },
    ..
]

```

Thus, a potential non code-golfed JavaScript function to calculate a working starting location is as follows (test fiddle):

```
function calculateStartingLocation(trackLength, fuelPitInfo) {
    for(i=0;;i++){
        var fuelPit = fuelPitInfo[i];
        var remainingFuelDistance = fuelPit.fuelDistance;
        for(j=i+1;;j++){
            var nextFuelPit = fuelPitInfo[j = j % fuelPitInfo.length];
            if (i == j) return fuelPitInfo[i].location;
            remainingFuelDistance -= (nextFuelPit.location - fuelPit.location + trackLength) % trackLength;
            if (remainingFuelDistance < 0) break;
            remainingFuelDistance += nextFuelPit.fuelDistance;
            fuelPit = nextFuelPit;
        }
    }
}

```

And the code-golfed function version (**140 chars**) is as follows (assuming `location` is replaced with `l` and `fuelDistance` is replaced with `d` in the provided `fuelPitInfo` object) (test fiddle):

```
function a(b,c){for(i=0;e=c[i],f=e.d;i++){for(j=i+1;g=c[j=j%c.length];){if(i==j++)return c[i].l;f-=(g.l-e.l+b)%b;if(f<0)break;f+=g.d,e=g;}}}

```
> 1 votes

# Answer
## D (98 chars)

the input is a int array with the amount of fuel with 0 if there is no fuel there

```
int f(int[] a){
    for(int s,r=-1,i=0;;i++){
        if(r+a.length==i)
            return r;
        if(--s<0){
            r=i;s=0;
        }
        s+=a[i%$];
    }
}

```

I start at index `0` with `0` fuel and whenever `s` falls below 0 I set that spot as my new start and reset `s` to `0`

if there is a solution you will find it in O(n) time or loop forever
> 1 votes

# Answer
## Python, 183

```
import sys
f=[map(int,_.split()) for _ in open(sys.argv[1])]
l=len(f)
s=[]
for i in range(l):
\tu,d=zip(*(f[i:]+f[:i]))
\tif all(sum(u[:j])<sum(d[:j])for j in range(l+1)):s+=[i]
print s

```

This program takes input in the form of a file consisting of N lines, where N is the number of fuel depots. Each line contains integers A and B, where A is the amount of fuel at the depot, and B is the distance to the next fuel depot. Example:

```
7 5
6 7
4 3

```

Output is the string representation of a list containing the indices of the fuel depots that are valid starting points. In this case, it outputs:

```
[0, 2]

```

Meaning that starting at either fuel depot 0, or fuel depot 2 will allow the vehicle to make it all the way around the circle.
> 1 votes

# Answer
# APL, 48 chars

```
{i/⍨{∧/0≤-\,m⊖⍨⍵-1}¨i←⍳↑⍴m←⍵[;2],⍪2-⍨/⍵[;1],100}

```

I'm not sure what the conditions are for this golf, but I wrote a straightforward O(n²) solution.

**Explanation**

This function accepts a matrix with the positions and amounts of fuel, with the condition that the length is 100 and that the first pit is at position 0:

```
      p
 0  6
 2 16
18  1
30 45
84  5
92 27

```

The first operation is to take the first column, append 100 at the end, and take the differences of each pair of values, to get the distances between each pair of pits:

```
      d←2-⍨/p[;1],100
      d
2 16 12 54 8 8

```

Then it builds a new matrix with the amounts of fuel in the first column and the distances in the second:

```
      m←p[;2],⍪d
      m
 6  2
16 16
 1 12
45 54
 5  8
27  8

```

Then it enumerates the naturals from 1 up to the number of rows (pits) and selects those which pass a given test:

```
      i←⍳↑⍴m
      ({ . . . }¨i)/i

```

The test is to rotate the rows of the matrix by the index amount minus 1, so let's say if we want to start from the 3rd pit, it rotates 2 rows from the top to the bottom:

```
      r←(3-1)⊖m
 1 12
45 54
 5  8
27  8
 6  2
16 16

```

Then it flattens the elements of the matrix in row-major order and it scans their alternating sum. Scanning means to compute the alternating sum of just 1, 2, 3… up to all the elements of the vector:

```
      a←-\,r
      a
1 ¯11 34 ¯20 ¯15 ¯23 4 ¯4 2 0 16 0

```

We can see that by starting from the 3rd pit the tank is first filled up to 1, then drained down to -11, then filled up to 34, and so on. The next step is to ascertain whether all the numbers are ≥0, which in this case they are not:

```
      ∧/0≤a
0

```

If they did, the starting position would be included in the resulting set of good starting positions. And that's all.

---

As somebody mentioned, one could probably compute this alternating sum just once and use the minima as starting positions. I'll do it as a second version.
> 1 votes

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