# Question
Title: Four weights to produce integer scale differences from 0 through 40 pounds
**Just-in-time edit**: I decided to reveal part of the answer and highlight a single aspect of the challenge.

---

Show how 4 weights, of 1, 3, 9, and 27 lbs. can be used to produce "weight differences" from 0 to 40 lbs.

You have a two - pan balance scale.

We define the **difference in pan weights** as the total weight placed on the left pan minus the total weight on the right pan.

The difference in pan weights for the empty scale is 0 lbs.

You have 4 rocks, a,b,c, and d, weighing 1, 3, 9 and 27 lbs respectively

Show how you can produce all integer weight differences from 0 to 40 lbs.

**Simpler example**:

*Problem*: With weights of 1 and 3 lbs. show how you can generate all weight differences from 0 to 4 lbs.

*Output*: for `a=1`, `b=3`;

>

---

For the 4 weight, 40 pound version, your output should consist of a table with columns displaying the weight difference, the symbolic amounts in each pan, and the absolute weights in each pan.

You may format the table in a way congenial to the language you are coding in.

*Scoring*: Shortest code wins

*Bonus*: 50% of your score if the same code can present the results for the case where 3, 4, and 5 weights are used (for 13, 40, and 121 lbs.)

# Answer
> 1 votes
## Python ~~124~~ 107 bytes * 50% = 53.5

```
f=lambda i,e=1:i and[e]*(i%3>1)+f(-~i/3,e*3)or[]
for i in range(3**4/2+1):r=f(-i),f(i);print i,map(sum,r),r

```

For different numbers of stones, replace the `4` in `range(3**4/2+1)` with any positive integer.

Sample output:

```
0 [0, 0] ([], [])
1 [1, 0] ([1], [])
2 [3, 1] ([3], [1])
3 [3, 0] ([3], [])
4 [4, 0] ([1, 3], [])
5 [9, 4] ([9], [1, 3])
6 [9, 3] ([9], [3])
7 [10, 3] ([1, 9], [3])
8 [9, 1] ([9], [1])
9 [9, 0] ([9], [])
10 [10, 0] ([1, 9], [])
11 [12, 1] ([3, 9], [1])
12 [12, 0] ([3, 9], [])
13 [13, 0] ([1, 3, 9], [])
14 [27, 13] ([27], [1, 3, 9])
15 [27, 12] ([27], [3, 9])
16 [28, 12] ([1, 27], [3, 9])
17 [27, 10] ([27], [1, 9])
18 [27, 9] ([27], [9])
19 [28, 9] ([1, 27], [9])
20 [30, 10] ([3, 27], [1, 9])
21 [30, 9] ([3, 27], [9])
22 [31, 9] ([1, 3, 27], [9])
23 [27, 4] ([27], [1, 3])
24 [27, 3] ([27], [3])
25 [28, 3] ([1, 27], [3])
26 [27, 1] ([27], [1])
27 [27, 0] ([27], [])
28 [28, 0] ([1, 27], [])
29 [30, 1] ([3, 27], [1])
30 [30, 0] ([3, 27], [])
31 [31, 0] ([1, 3, 27], [])
32 [36, 4] ([9, 27], [1, 3])
33 [36, 3] ([9, 27], [3])
34 [37, 3] ([1, 9, 27], [3])
35 [36, 1] ([9, 27], [1])
36 [36, 0] ([9, 27], [])
37 [37, 0] ([1, 9, 27], [])
38 [39, 1] ([3, 9, 27], [1])
39 [39, 0] ([3, 9, 27], [])
40 [40, 0] ([1, 3, 9, 27], [])

```

The basic operating principle, is that the problem is analog to converting a number into ternary. In Python, this is a one liner:

```
f=lambda i:i and i%3+f(i/3)*10

```

Of course, we're working in a slightly different base. Instead of the values `0, 1, 2` we use `-1, 0, 1`. This means when `i%3 == 2`, this should really be `-1` (calculated by `(i+1)%3-1` or `-~i%3-1`), and the value of the `i` sent to the next iteration needs to be adjusted accordingly.

More specifically, if `d=(i+1)%3-1`, then the value of `i` sent to the next iteration should be `(i-d)/3`. However, this calculaion can be simplified greatly using integer division, to just `(i+1)//3`. Rationale: if `d == 0`, then `i` was already a multiple of `3`, and adding one won't change the integer quotient. If `d == 1`, then we should be subtracting `1` to make `i` a multiple of 3, but if we add `1` instead, it will now be `2 (mod 3)`, which won't change the integer quotient either. If however `d == -1`, then we do in fact need to add `1` to reach the next multiple of `3`. Therefore, by using integer division, all three cases can be simplified to adding `1`.

One thing that makes this problem interesting is that the negative and positive values need to be separated into different baskets. I decided the best way to accomplish this is to only collect the positive values, and then call the function again with `-i`, which will obviously have its stones reversed. This also allows me to save the `-~i%3` calculation entirely, since I know what its value will be.

# Answer
> 4 votes
## APL 198 * 50% = 99

```
z←W n
l←⍉(n⍴3)⊤w←0,⍳+/b←3*0,⍳n-1
r←(⍴l)⍴0
:while 0≠+/+/l>1
    r←r+l>1
    l←((l≤1)×l)+1⌽l>1
:end
a←' ',⌽⎕av[97+⍳n]
c←(⍴l)⍴⍳n
b←0,⌽b
z←l≠r
l←z×l
r←z×r
l←1+l×c
r←1+r×c
z←w,'{',a[l],'}','{',a[r],'}','{',b[l],'}','{',b[r],'}'

```

As we are effectively working in base three the arithmetic is fairly trivial and is complete by the end of the while loop where the arrays l and r are the contents of the left and right scale pans respectively in base three. This takes about 80 characters. The rest is formatting the output which I am sure can be improved.

To run simply type W followed by the number of weights you want to use. Below is a sample output for n=3:

```
 W 3
 0 {   }{   }{ 0 0 0 }{ 0 0 0 }
 1 {  a}{   }{ 0 0 1 }{ 0 0 0 }
 2 { b }{  a}{ 0 3 0 }{ 0 0 1 }
 3 { b }{   }{ 0 3 0 }{ 0 0 0 }
 4 { ba}{   }{ 0 3 1 }{ 0 0 0 }
 5 {c  }{ ba}{ 9 0 0 }{ 0 3 1 }
 6 {c  }{ b }{ 9 0 0 }{ 0 3 0 }
 7 {c a}{ b }{ 9 0 1 }{ 0 3 0 }
 8 {c  }{  a}{ 9 0 0 }{ 0 0 1 }
 9 {c  }{   }{ 9 0 0 }{ 0 0 0 }
10 {c a}{   }{ 9 0 1 }{ 0 0 0 }
11 {cb }{  a}{ 9 3 0 }{ 0 0 1 }
12 {cb }{   }{ 9 3 0 }{ 0 0 0 }
13 {cba}{   }{ 9 3 1 }{ 0 0 0 }

```

# Answer
> 3 votes
## Python, 160 * 50% = 80

```
def f(n):
 for i in range(3**n/2+1):g=lambda z:'+'.join(`3**x`for x in range(n)if(i+3**x/2)/3**x%3==z)or'0';print i,'[%s, %s]'%(g(1),g(2)),map(eval,(g(1),g(2)))

```

Shows how each weight difference can be produced, given 'n' different weights.

# Answer
> 0 votes
## Perl, 201 (or 166) chars + 50% bonus = 100.5 (or 83)

eek, brute forcing this turned out to be more complex than i anticipated. im interested to see others' certainly more analytical approaches

change the problem size by modifying the value of `$j` defined at the top to 3, 4, or 5.

this will demonstrate *all* ways to generate the differences, not any pairs in particular.

some additional characters are used to print the differences in order. otherwise, you can remove the outer `for$n(0..$s){}` loop and the `$$x[$j]-$$_[$j]==$n` test to save 14+21 chars for a total of 166 chars.

```
$k=($j=4)-1;@a=map{$s=0;$s+=$_ for@$_;[@$_,$s]}map{$c=$_;[map{$c&1<<$_&&3**$_}0..$k]}0..2**$j-1;for$n(0..$s){for$x(@a){$$x[$j]-$$_[$j]==$n&&print"$n {@$x[0..$k],@$_[0..$k]} {$$x[$j],$$_[$j]}",$/for@a}}

```

or slightly more formatted (no more readable):

```
# set $j to the problem domain size
$k = ($j = 4) - 1;

# gather up all possible combinations and their sums
@a = map{ $s=0; $s+=$_ for @$_; [@$_,$s] } map { $c=$_; [map { $c & 1<<$_ && 3**$_ } 0..$k] } 0 .. 2**$j-1;

# walk through the pairs of combinations and find the differences
for $n (0..$s)
{
  for $x (@a)
  {
    $$x[$j] - $$_[$j] == $n &&
      print "$n {@$x[0..$k],@$_[0..$k]} {$$x[$j],$$_[$j]}", $/ for @a
  }
}

```

---
Tags: code-golf
---


title: "Defragmenting" a list

text:
# Question
Title: "Defragmenting" a list
A fragmented file is a file which is seperated into several parts on a harddrive, because it can't fit into a certain space.

On all harddrives, there are files called unmovable files, which are unmovable. To simulate real data on a harddrive, the input will also have unmovable files.

You are given several sequences of consecutive numbers, all scrambled into one list. The goal is to order each of these sequences so that they are placed in as little space as possible. *The list can be as big as you need it to be.* If there is no space for a sequence, then put a `-` instead.

To mark the unmovable files, another list, with the same length as the data, will be given after you recieve the data. It will contain either a 0 or a 1. Every 1 within that list means that the corresponding item in the data is unmovable.

Shortest code wins.

**Test Cases**

The output does not have to be exactly like this, but the length needs to be the same, and all of the sequences need to be ordered.

```
[ 0,  0,  1,  1,  1,  1,  0,  0,  0,  0,  0]
[25, 30, 11, 12, 13, 14, 68, 69, 31, 26, 32]
Output: [25, 26, 11, 12, 13, 14, 68, 69, 30, 31, 32]
(output length: 11)

[0, 0, 0,  0, 0,  1,  1,  1, 0, 0,  0,  0,  0,  0,  0, 0]
[2, 3, 5, 14, 8, 10, 11, 12, 4, 6, 28, 30, 29, 15, 16, 7]
Output: [14, 15, 16, -, -, 10, 11, 12, 2, 3, 4, 5, 6, 7, 8, 28, 29, 30]
(output length: 18)

```

# Answer
> 6 votes
## APL (~~132~~ ~~126~~ ~~123~~ ~~147~~ ~~145~~ 143)

This was a bit harder than I thought it'd be :)

Edit: the hard drive is infinite :S. All sequences that could not fit in the original space, are now appended onto the end of the output.

```
F←⍬⋄{×⍴⍵:∇1↓⍵⊣{∨/P←S⍷⍨1⍴⍨⍴⍵:S[R]∘←0⊣D[R←1-⍨(⍳⍴⍵)+⌊/P/⍳⍴P]∘←⍵⋄F∘←F,⍵}⊃⍵⋄D[S/⍳⍴S]∘←'-'}G[⍒⊃∘⍴¨G←K⊂⍨1≠|-⌿K,[÷2]¯1⌽K←K[⍋K←(S←~⎕)/D←⎕]]⋄F,⍨D/⍨~⌽∧\⌽S

```

This is what it does to your 1st and 2nd example ~~(the 2nd example is different, but in your example the output length is not the same as the input length and you said in a comment it was wrong, so...)~~

```
⎕:    25 30 11 12 13 14 68 69 31 26 32
⎕:    0  0  1  1  1  1  0  0  0  0  0
25 26 11 12 13 14 30 31 32 68 69

```

```
⎕:    2 3 5 14 8 10 11 12 4 6 28 30 29 15 16 7
⎕:    0 0 0 0  0 1  1  1  0 0 0  0  0  0  0  0
14 15 16 - - 10 11 12 2 3 4 5 6 7 8 28 29 30

```

Explanation:

* `F←⍬`: set `F` to the empty list. This will hold the overflow.
* `K←K[⍋K←(S←~⎕)/D←⎕]`: read two lists. The first list (numbers) is stored in `D`. The second list (whether the data is unmovable) is *inverted* and then stored in `S`. Get all movable numbers, and sort them. Store this in `K`.
* `G←K⊂⍨1≠|-⌿K,[÷2]¯1⌽K`: Subtract each element of `K` from the next element of `K`. Wherever this is not 1, we found the beginning of a new sequence. Store the list of sequences in `G`.
* `G[⍒⊃∘⍴¨G`...`]`: sort the list of sequences by descending length. This way, we place the longest sequences first.
* `{×⍴⍵:...}G`: as long as this list of sequences is not empty...
* `∇1↓⍵⊣`: handle the tail of the list, after...
* `{...}⊃⍵`: doing the following with the head:
* `∨/P←S⍷⍨1⍴⍨⍴⍵`: find, in `S`, a list of ones that is as long as the current sequence ().
* `S[R]∘←0⊣D[R←1-⍨(⍳⍴⍵)+⌊/P/⍳⍴P]∘←⍵`: if there is one, store  in `D` at the first position that it fits, and mark these positions as unmovable in `S`.
* `⋄F∘←F,⍵`: if there is no room, add it to the overflow.
* `⋄D[S/⍳⍴S]∘←'-'`: when we're at the end of the list of sequences, all positions where `S` is still one are places where we couldn't put anything. Mark these with `-`.
* `⋄F,⍨D/⍨~⌽∧\⌽S`: then, at the end, display D, with the trailing `-`s removed, followed by the overflow (`F`) per the new rules.

# Answer
> 0 votes
I decided to tackle this solution in Scala, taking advantage of both functional and imperative features of the hybrid language. Here is the code for my solution.

```
def orderedSequences(filePieces: List[(Int,Int)]): List[List[(Int,Int)]] = {
  def orderedSequencesR(filePieces: List[(Int,Int)], currentSequence: List[(Int,Int)], sequences: List[List[(Int,Int)]]): List[List[(Int,Int)]] = {
    if(filePieces == Nil) sequences :+ currentSequence
    else if(currentSequence == List.empty) orderedSequencesR(filePieces.tail, List(filePieces.head), sequences)
    else if(filePieces.head._2 == currentSequence.last._2 + 1) orderedSequencesR(filePieces.tail, currentSequence :+ filePieces.head, sequences)
    else orderedSequencesR(filePieces, List.empty, sequences :+ currentSequence)
  }
  orderedSequencesR(filePieces, List.empty, List.empty)
}

def defragment(sequences: List[List[(Int,Int)]], filePieces: List[(Int,Int)]): List[Any] = {
  val largestSequenceLength = sequences.flatten.length
  var solution = scala.collection.mutable.ListBuffer[(Int,Int)]()

  filePieces foreach {filePiece => if(filePiece._1 == 1) solution += filePiece  else solution += ((-1,0))}

  solution ++ Iterator.fill(largestSequenceLength)((-1,0))

  sequences foreach {
      sequence =>
      var sequenceIsInserted = false
      var currentPosition = 0
      while(!sequenceIsInserted) {
        if(solution.slice(currentPosition,currentPosition + sequence.length).forall((s: (Int,Int)) => s._1 == -1)){
          solution = solution.slice(0,currentPosition) ++ sequence ++ solution.slice(currentPosition + sequence.length, solution.length)
          sequenceIsInserted = true
        }
        currentPosition += 1
      }
  }

  solution.map(_._2).toList
}

def getDefragmentedFiles(isUnmovable: List[Int], files: List[Int]) = {
    val filePieces = isUnmovable zip files
    val sequences = orderedSequences(filePieces.filter(os => os._1 == 0).sortBy(t => t._2))
    val bestSolution = defragment(sequences.permutations.toList.sortBy {b => defragment(b, filePieces).length}.head, filePieces)
    println(bestSolution map { case 0 => '-'; case x => x })
}

val isUnmovable = List(0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0)
val files = List(2,3,5,14,8,10,11,12,4,6,28,30,29,15,16,7)
getDefragmentedFiles(isUnmovable, files)

```

I take the list of movable/unmovable positions along with the files and zip them up. I then get the movable files, sort them in order, and pass them into orderedSequences to get a list of file sequences.

Once I get the sequences, I get all the permutations of the sequences and I brute-force defrag them, taking the solution of the shortest length. This is pretty inefficient, but I can't think of a more efficient solution right now. The defrag method takes each sequence, in order, and iterates through the memory space until a valid spot to place the sequence is found.

After getting the best solution, I prettify it and print it out as a list.

---
Tags: code-golf
---


title: There Was A Stream

text:
# Question
Title: There Was A Stream
# Challenge

Write a program that generates the song "There Was A Stream", detailed below.

## Description

The song "There Was a Stream" is a camping song. It takes N parameters and generates a song of length O(N2) lines. A sample song (first 3 verses) is given here.

## Rules

* Your entry must take a list of strings and output a valid song. It may be a function (that takes an array of strings) or a program (that takes strings from ARGV or STDIN). Output may be a return value or output to STDOUT or STDERR.
* It must run within 1/2 second on my machine (1.66GHz Intel Atom, 1GB RAM, Ubuntu 12.04) for all invocations with less than 15 parameters.
* Verses must be separated by a blank line.
* No inbuilt compression function (e.g. gzip), whether from the core or from libraries. Things like `rot13`, `md5`, `base64` etc. are okay though.
* You may include a data file (that is placed in the same directory and named whatever you wish), but its score will be added to the total for the program.

### Scoring

Count the number of characters (if you use ASCII) or raw bytes (if you use something else).
Command-line flags (without the hyphens) are included, but not the interpreter name, for example `#!/usr/bin/perl -n` adds 1 to the character count. All whitespace is included.
As with all code-golf, the entry with the lowest character count wins.
**Deadline:** 14 December 2012

## Example

```
INPUT: bank house
OUTPUT: (given above)
```

Reference implementation (ungolfed, very ugly code): http://pastebin.com/VeR4Qttn

# Answer
## Perl 239 + 2 = 241 bytes

This is a mostly binary solution, so as usual, this is a program to generate it:

generator.pl

```
use MIME::Base64;

$data = <<EOD;
JF89bGMgcGFjayB1NjAsJ8MqbtCBITBInQmKJcpWt4c2oWhLBPwjAkyBIiUwjBI3Ql9c9GoWtJZbuTd5
ZbuWhPwjAkyBIyQjDBFXQlLpGtKJWhP2t4c2r7mhFQjAqdM2t4eTjjk2aJcpWtKJWrb77ms6Kbpc2qKZ
6E1rmtKJWo7JYcmorNZWhM6+U1LpGobLGt4c2osqZ6NGobpGp4eTk0wiTBIXQlLpGr7mtKIdGhPwjBIT
nQkyBISUwjBFXQtKJWhPxAjBLHR7KdNLJWh5r8ms9MpYbTIFQyc7eS8zLTovCkFGSUpUVyAvO2V2YWw=
EOD

print decode_base64($data);

```

Accepts input from STDIN, space separated, two extra bytes for the `-na` option. Sample usage:

```
$ perl generator.pl > out.pl

$ stat -c %s out.pl
239

$ echo bank house | perl -na out.pl
There was a stream
(There was a stream)
Just a teeny-weeny stream
(Just a teeny-weeny stream)
And the stream was on its way...
Where the moon shines high
In the clear blue sky
And all was bright and gay.

And on that stream
(And on that stream)
There was a little bank
(There was a little bank)
Just a teeny-weeny bank
(Just a teeny-weeny bank)
And the bank was on the stream
And the stream was on its way...
Where the moon shines high
In the clear blue sky
And all was bright and gay.

And on that bank
(And on that bank)
There was a little house
(There was a little house)
Just a teeny-weeny house
(Just a teeny-weeny house)
And the house was on the bank
And the bank was on the stream
And the stream was on its way...
Where the moon shines high
In the clear blue sky
And all was bright and gay.

```

### Method

Consider the following UU-Encoded string:

```
\PRINT($A,$B="8HERE:WAS:A:$L$_","3($B)3",$C="7UST:A:TEENY-WEENY:$_","3($C)",,$5="
\4ND:THE:$_:WAS:ON:$5","ITS:WAY...39HERE:THE:MOON:SHINES:HIGH36N:THE:CLEAR:BLUE:$
\SKY34ND:ALL:WAS:BRIGHT:AND:GAY.33"),$A="4ND:ON:THAT:$_",$A.="3($A)3",$5="THE:$_$
5",$L='LITTLE:'FOR:STREAM,@5#

```

After applying a `lc,y/3-:/\nAFIJTW /` it becomes this:

```
\print($a,$b="There was a $l$_","
($b)
",$c="Just a teeny-weeny $_","
($c)",,$F="
\And the $_ was on $F","its way...
Where the moon shines high
In the clear blue $
\sky
And all was bright and gay.

"),$a="And on that $_",$a.="
($a)
",$F="the $_$
F",$l='little 'for stream,@F#

```

Which is basically the 269 byte solution below.

There's a few problems with this method, though. UU-Encoded strings are limited to characters 33-96, which excludes space, newline, and `{ | } ~`, as well as all lower-case letters. The solution I chose, is to apply `lc` after the `pack u`, and then translate 8 characters: space, newline, and the 6 upper-cased I needed. This leaves an 18 byte footprint, which is fairly excessive, but it produces the desired result.

The other problem is that each line needs to begin with the same character (here I chose `\` corresponding to a *decoded* length of 60 (92 - 32), which is an *encoded* length of 80), except for the last line, which needs to begin with the character reflecting its length. Here I ended up with 21 (padding with a `#` to be evenly divisible by 3), corresponding to `5`. No problem, I'm replacing 5 anyway, so I chose it as one of my variables. Perl seems to be incredibly lenient about where you can place backslashes. This program even begins with one.

It is possible to instruct perl to use a other characters to begin each line, such as `M` (the default value), but none seem quite as flexible as a backslash. As an aside, this method should be equally as effective in Ruby. If I had any skill in the language, I might be tempted to try it.

For reference, my previous solutions remain below.

---

## Perl 267 + 2 = 269 bytes

```
(print$a,$b="There was a $l$_","
($b)
",$c="Just a teeny-weeny $_","
($c)",$d="
And the $_ was on $d",'its way...
Where the moon shines high
In the clear blue sky
And all was bright and gay.

'),$a="And on that $_",$a.="
($a)
",$d="the $_$d",$l='little 'for stream,@F

```

Accepts input from STDIN, space separated, two extra bytes for the `-na` option. Sample usage:

```
$ echo bank house | perl -na stream-song.pl

```

---

## PHP 286 bytes

No real attempt at compression, just output reusage.

```
<?for($w=stream;$w;$a="And on that $w",$a.="
($a)
",$l='little ',$d="the $w$d",$w=next($argv))echo$a,$b="There was a $l$w","
($b)
",$c="Just a teeny-weeny $w","
($c)",$d="
And the $w was on $d",'its way...
Where the moon shines high
In the clear blue sky
And all was bright and gay.

';

```

Accepts input as command line arguments. Sample usage:

```
$ php stream-song.php bank house

```
> 4 votes

# Answer
## Haskell, 366 characters

```
t="stream"
b o="And the "++o++" was on "
p s=[s,'(':s++")"]
a(o:q@(p:_))=(b o++"a "++p):a q
a[o]=[b o++"its way..."]
v l@(o:q)=w q++p("There was a "++if o==t then o else"little "++o)++p("Just a teeny-weeny "++o)++a l++["Where the moon shines high","In the clear blue sky","And all was bright and gay.",""]
w m@(y:_)=v m++p("And on that "++y)
w[]=[]
s=v.reverse.(t:)

```

As permitted by the problem statement, this is a function `s :: [String] -> String`, where the input is the objects and the return value is a list of lines of the song.

This is nowhere near the current leader in this challenge, but it's as far as I got and I thought someone might like to see if it can be improved. I think its main failing is trying too hard to capture all of the structure of the song in the structure of the program. It also might be interesting to rewrite it to use lists of words (replace `++` with `,` and fewer spaces), or `\n`s rather than a list of lines.

Fluffy source:

```
stream="stream"
andthe o="And the "++o++" was on "
p s=[s,'(':s++")"]

ander :: [String] -> [String]
ander(o:os@(p:_))=(andthe o++"a "++p):ander os
ander[o]=[andthe o++"its way..."]

outerVerse :: [String] -> [String]
outerVerse l@(o:os)=recurse os++p("There was a "++if o==stream then o else"little "++o)++p("Just a teeny-weeny "++o)++ander l++["Where the moon shines high","In the clear blue sky","And all was bright and gay.",""]

recurse :: [String] -> [String]
recurse m@(y:_)=outerVerse m++p("And on that "++y)
recurse[]=[]

song=outerVerse.reverse.(stream:)
go xs = putStr $ unlines $ song xs

```

Defluffifier (in Perl):

```
#!/usr/bin/perl -wp

s/ ?\+\+ ?/++/g;
s/ander/a/g;
s/andthe/b/g;
s/iverse/i/g;
s/song/s/g;
s/stream(?!")/t/g;
s/\bos\b/q/g;
s/outerVerse/v/g;
s/recurse/w/g;
s/ends/z/g;

s/^go .*//s;
s/--.*//s;
s/^\s\Z//s;
s/^.*::.*\Z//s;

```
> 2 votes

# Answer
**Python 2.7 352 Bytes**

```
import urllib as u;import re,sys;v=sys.argv;f=lambda l,o,n:[re.sub(o,n,i) for i in l];n='\n';d=-1;m=re.findall('i\d.+>(.+)</d',u.urlopen('http://goo.gl/48fMV').read());a=m[:8]+[n];z=range;s='stream'
for t in z(len(v)+d):a+=f(m,s,v[t])[9:11]+f(m,s,'little '+v[t+1])[:4]+['And the '+v[i+1]+' was on a '+v[i] for i in z(t,d,d)]+m[4:8]+[n]
print n.join(a)

```

Example usage:

```
python stream bank house

```

Output:

```
There was a stream
(There was a stream)
Just a teeny-weeny stream
(Just a teeny-weeny stream)
And the stream was on its way...
Where the moon shines high
In the clear blue sky
And all was bright and gay.

And on that stream
(And on that stream)
There was a little bank
(There was a little bank)
Just a teeny-weeny little bank
(Just a teeny-weeny little bank)
And the bank was on a stream
And the stream was on its way...
Where the moon shines high
In the clear blue sky
And all was bright and gay.

And on that bank
(And on that bank)
There was a little house
(There was a little house)
Just a teeny-weeny little house
(Just a teeny-weeny little house)
And the house was on a bank
And the bank was on a stream
And the stream was on its way...
Where the moon shines high
In the clear blue sky
And all was bright and gay.

```

Un-golfed (also added a few `a+=`s):

```
#!/usr/bin/env python

import urllib as u
import re
import sys

v=sys.argv

f=lambda l,o,n: [re.sub(o,n,i) for i in l]

n='\n';
d=-1;
m=re.findall('i\d.+>(.+)</d',u.urlopen('http://goo.gl/48fMV').read())
a=m[:8]+[n]
z=range
s='stream'

for t in z(len(v)+d):
    a+=f(m,s,v[t])[9:11]
    a+=f(m,s,'little '+v[t+1])[:4]
    a+=['And the '+v[i+1]+' was on a '+v[i] for i in z(t,d,d)]
    a+=m[4:8]+[n]
print n.join(a)

```
> 1 votes

---
Tags: code-golf
---


title: Prune connections

text:
# Question
Title: Prune connections
John is writing a program that finds the best route from A to B using public transport. For a given pair of origin and destination the program calculates a set of routes with departure time and arrival time, such as this:

```
10:12 11:45
10:15 11:50
10:22 12:05
10:25 12:00

```

As you see, the output may include a few routes that are superfluous in the sense that there is another route that starts later and ends earlier. Such routes are certainly never wanted by the user since he cat get out later to arrive sooner.

Your task, if you choose to accept it, is to write a program that prunes a set of routes such that all superfluous rules are eliminated.

## Input

The input is a list of newline separated pairs of whitespace separated departure and arrival time in military format (hh:mm). Such a pair is called a *route*.

You may assume that all times are in the same day and that the arrival time is always later than the departure time. You may also assume that the list is orderer by departure times.

## Output

The output is the same list as the input without redundant routes. A redundant route is a route for which another route exists in the list that has a later departure and an earlier arrival time. There must exist an order to remove all redundant routes such that in each step you can show the route that makes the removed route redundant. You don't have to output that order.

## Extra credit

Prove or disprove that for each list of input routes there exists exactly one set of output routes.

## Restriction

* Usual codegolf rules apply

## Scoring

To score, apply the function that gives an upper bound to your solutions complexity with your solution's total number of characters. Normalize your bounding function such that a solution length of two character yields a score of two.

For example, if your solution has 24 characters and a complexity of *O(2n)*, your score is 4194304. If your solution has 123 characters and a complexity of *O(n2)* your score is 7564. If your solution has 200 characters and a complexity of *O(n\**log*n)*, your score is 734.

I use this scoring method in order to encourage people to implement efficient solutions.

# Answer
> 2 votes
### GolfScript, 26 characters, 26 score

```
n%-1%{6>[0$m]$0=:m=},-1%n*

```

The solution assumes a list sorted on departure time on input (as noted in the problem description) and also prints a sorted list (if this restriction can be dropped we may save 3 chars).

The code traverses the list backwards and removes any connection where the arrival time is larger than the minimum arrival time processed so far.

```
n%            # split input at newlines
-1%           # reverse list
{             # filter list...
   6>         # take arrival time of current item
   [0$m]      # make an array consisting of that arrival time and the minimum
              # up to now, contained in variable m. Note since m is not initialized
              # the array will consist of a single item in the first iteration
   $          # sort that array (consisting of one or two items)
   0=         # take first item, i.e. minimum arrival time
   :m         # save to variable m
   =          # compare current item to m and select if both are equal
},            # ... end of filter list
-1%           # reverse list again
n*            # join items with newline

```

The code can be tested online.

# Answer
> 3 votes
## Perl 47 (+1) bytes • O(n) ⇒ 48 score

```
$#a-=2until$a[-/ \K/]lt$';push@a,$`,$'}{print@a

```

Adding one byte for the `-n` option, as per the OP's instructions.

Sample input:

```
10:30 11:00
10:33 11:18
10:42 11:10
10:47 11:18
10:49 11:26
10:50 11:09
11:00 11:20
11:01 11:28
11:11 11:31
11:21 11:49
11:23 11:53
11:29 12:09
11:36 12:08
11:41 12:15
11:46 12:06
11:53 12:23
11:56 12:32
12:01 12:30
12:04 12:47
12:05 12:25

```

Sample output:

```
$ perl -n prune-connections.pl < in.dat
10:30 11:00
10:50 11:09
11:00 11:20
11:01 11:28
11:11 11:31
11:21 11:49
11:23 11:53
11:46 12:06
11:53 12:23
12:05 12:25

```

Input generator (PHP):

```
<?php
  for($t = strtotime('10:30'); 20 > $i; $i++) {
    $r = rand(15, 45)*60;
    echo date('H:i', $t), ' ', date('H:i', $t+$r), PHP_EOL;
    $t += rand(0, 10)*60;
  }
?>

```

**Lemma:**
If a route is invalidated by some other route where , and no other route between and invalidates , then invalidates all routes from to .

Because the routes are sorted by departure time, and , must necessarily have a later departure time than . Then, in order to invalidate , needs only to have an earlier arrival time. If there were a route between and which was not invalidated by , it would have an earlier arival time than , and hence, would have already invalidated .

Therefore, a linear time algorithm, which only checks if the current route invalidates the previous route is sufficient to solve the problem. When an invalidation is found, the route before the invalidated route must also be checked, until a route is not invalidated (or no valid routes remain). Because a route can only be invalidated once, no more than routes will be invalidated in this manner.

Note that it is important that the invalid routes actually be *removed* from the list. If they are simply marked invalid (or set to `null`, etc.), this will result in complexity, in the case that each new route invalidates all previous routes.

Proof that only one solution exists follows directly from the law of transitivity. If a route is invalidated by , and is invalidated by , is also invalidated by . In order for multiple solutions to exist, it must be possible to invalidate without invalidating , but any route that invalidates will also invalidate , and will lead to the same solution.

# Answer
> 1 votes
## APL ~~107~~ ~~57~~ 52 . O(n) = 52

```
T m
r←m
m←⍎(,0 5↓m)~':'
l:m←(n←(2≤/m),1)/m
r←n⌿r
→(~×/n)/l
r

```

The input m variable could be simply typed in as follows for the first example below:

```
m←4 11⍴'10:12 11:4510:15 11:5010:22 12:0510:25 12:00'

```

or it could be read in programatically from a number of sources eg text file.

The line before the start of the loop converts the character input (m) of arrival times to 4 digit numbers. The loop is then using sequential ≤ on those times to do the pruning. Tested on the following:

```
10:12 11:45  10:12 11:45  10:12 11:45  10:12 11:45
10:15 11:50  10:15 11:50  10:15 11:50  10:15 11:50
10:22 12:05  10:22 12:05  10:22 12:05  10:22 12:05
10:25 12:00  10:25 12:00  10:25 12:00  10:25 12:00
===========  10:30 11:55  10:30 11:55  10:30 11:55
10:12 11:45  ===========  10:35 12:10  10:35 12:10
10:15 11:50  10:12 11:45  ===========  10:40 11:40
10:25 12:00  10:15 11:50  10:12 11:45  ===========
             10:30 11:55  10:15 11:50  10:40 11:40
                          10:30 11:55
                          10:35 12:10

```

# Answer
> 1 votes
## Python 82 • O(n) = 82

New to code golfing. Dunno if I am breaking any rules.

```
i=-1
while len(a)>-i:
 if a[i][6:]<a[i-1][6:]:a.pop(i-1)
 else:i-=1
print ''.join(a)

```

The algorithm is to iterate from the back of the list, removing the previous line if it has a later arrival time or moving the pointer to the previous line otherwise.

Note: The definition of redundant routes given by the OP is taken to the word, so neither of the two routes which have the same arrival times but different departure times are removed.

---
Tags: code-golf
---


# Question
Title: Convert the Binary Champernowne Constant to Decimal
The Champernowne constant is a transcendental decimal number whose digits are the concatination of all positive integers.

C10 = `0.12345678910111213141516...`10

The binary version of this is

C2 = `0.1101110010111011110001...`2

Write a program that prints C2 in decimal. The program should never halt. It should continue printing digits such that given infinite time and memory, it will print an infinite number of correct digits.

To illustrate this, you must account for integer overflow, since integer overflow will either cause an error or print incorrect digits, even with infinite memory available.

To test your code, here are the first 150 digits of this number.

```
0.862240125868054571557790283249394578565764742768299094516071214557306740590516458042038441438618133400466718933678923129464456214392016383510596824661

```

Shortest code wins.

# Answer
> 5 votes
## Python 119 bytes

```
import sys
r=i=n=0
while 1:
 i+=1
 for b in bin(i)[2:]:n+=1;r=r*10+int(b)*5**n;~n%4or sys.stdout.write(('0.'+`r`)[n/4])

```

Given unlimited memory, this will run indefinitely, although it does slow down quite a bit after the first few thousand digits.

Each binary bit is treated as its corresponding power of 5, i.e:
*0.1 ⇒ 5, 0.01 ⇒ 25, 0.001 ⇒ 125, 0.0001 ⇒ 625, etc.*

Which lends itself nicely to a decimal conversion, as:
*1/2 = 0.5, 1/4 = 0.25, 1/8 = 0.125, 1/16 = 0.0625, etc.*

The variable `r` stores a running total of all bits so far (increasing by a factor of 10 each iteration), and every four bits the next digit is output. This is mathematically correct, because

```
log<sub>2</sub>(10) ≈ 3.321928
```
which means that every `3.32` or so binary bits will produce one decimal digit. `10/3` is a better upper bound, but I chose `4` for sake of brevity.

## Ruby 80 bytes

```
r=i=n=0
$><<gsub(/./){"0.#{r=r*10+$&.to_i*5**n+=1}"[n/4,n%4/3]}while$_='%b'%i+=1

```

Same algorithm as above. It's been a while since I've golfed Ruby, so I may be missing a few tricks.

## GolfScript 53 bytes

```
0:µ.{).2base{5µ):µ?*@10*+.'0.'\+µ4/<µ(4/>print\}/.}do

```

Once again, same algorithm. This is one of the first things I've ever written in GolfScript, so I'm fairly certain that it can be reduced further. I've chosen to use `µ` (char 181) as a variable name, because it saves a whitespace in the expression `µ4/`.

# Answer
> 2 votes
# Mathematica 73 65 85

**Edit**:

```
s = {}; n = 1; While[n < 50, s = Join[s, IntegerDigits[n, 2]];
Print[N[FromDigits[{s, 0}, 2], n]]; n++]

```

Explanation:

`s` holds the base-2 digits of 1, 2, 3,...n, as a list of digits, `{1,1,0,1,1,1,0,0,...}`. Then `FromDigits` inserts the decimal point (with the `2` indicating the position), treating the input as a base-2 decimal and generating a base-10 decimal as output.

---

Using the built-in function: 51 chars

```
n=1;While[True,Print@N[ChampernowneNumber@2,n];n++]

```

# Answer
> 1 votes
## Python, 225

```
import sys,fractions
w=sys.stdout.write
w('0.')
h=t=10
l=n=0
p=fractions.Fraction(5)
i=int
while 1:
 while i(h)!=i(l):
  n+=1
  for c in bin(n)[2:]:
    if c=='1':l+=p
    else:h-=p
    p/=2
 w(str(i(h)));h-=i(h);l-=i(l);h*=t;l*=t;p*=t

```

Note that the 4-space indentation should be tab characters. They seem to be converted to spaces when displayed here.

**Explanation**

`h` and `l` are the highest and lowest possible values for the current digit, as fractions.

For example, if h is `7/2` or `3.5`, the current digit is at most 3, and if it is 3, then the next digit is at most 5.

When `int(h) == int(l)`, we know what the next digit is, so we print that, subtract it from h and l, and multiply them by 10 to get the bounds for the next digit.

When `int(h) != int(l)`, we improve our bounds by looking further into C2. For the nth decimal place in the output and bth binary place in C2, a `1` means `l` increases by `10^n/2^b` and a `0` means `h` decreases by that amount.

# Answer
> 1 votes
### GolfScript, 71 characters

```
1.0.){:q,{\.+)q*+\.+q*\.)3$*2$/1$4$*3$/:&-!{&10%print@10*@@}*}/q.+s}:s~

```

Maybe not the best puzzle for GolfScript but tried a solution anyways. The code does iterates infinitely due to an unlimited recursion and prints the digits one after the next (one of the rare cases where the `print` built-in is needed).

Note that the online version has a cutoff for the recursion.

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


title: Naming ionic compounds

text:
# Question
Title: Naming ionic compounds
An ionic compound is named like so: `(metal name) (non-metal suffixed with -ide)`. Here is a list of all the suffixes that need to be replaced with `-ide`:

```
-on -ogen -ygen -ine -orus -ur -ic -ium

```

The number of atoms of each element in the compound is not used in naming ionic compounds. Ignore the multivalent metal naming rules.

```
NaCl -> sodium + chlorine -> sodium chloride.
K2S -> potassium + sulphur -> potassium sulphide (or sulfide).
Yb2P3 -> ytterbium + phosphorus -> ytterbium phosphide.
PbTe2 -> lead + tellurium -> lead telluride.

```

A string containing an ionic compound (`NaCl`, `K2S`, `Yb2P3`) will be given as input. No polyatomic ions will be given. The program has to output the name of this compound.

Since nobody wants to compile the periodic table data themselves, here is a paste that has the names, symbols, and whether or not it is a metal of each element, in this order: `(name) (symbol) (is metal?)`. You can save this to an external file (the length of the file will not be counted), or you can store the data within your program (just discount the length of that string from there.) You may not need all the information provided. Every element is seperated by a newline.

As always with code golf challenges, shortest code wins.

# Answer
## **Ruby, 114**

```
f,s=$*[0].split /\d*(?=[A-Z]|\Z)/
puts (n=Hash[*<<X.split-%w[0 1]].invert)[f]+" "+n[s].sub(/(i..|.gen|..)\Z/,"ide")
Hydrogen H 0
Helium He 0
Lithium Li 1
Beryllium Be 1
Boron B 0
Carbon C 0
Nitrogen N 0
Oxygen O 0
Fluorine F 0
Neon Ne 0
Sodium Na 1
Magnesium Mg 1
Aluminium Al 1
Silicon Si 0
Phosphorus P 0
Sulfur S 0
Chlorine Cl 0
Argon Ar 0
Potassium K 1
Calcium Ca 1
Scandium Sc 1
Titanium Ti 1
Vanadium V 1
Chromium Cr 1
Manganese Mn 1
Iron Fe 1
Cobalt Co 1
Nickel Ni 1
Copper Cu 1
Zinc Zn 1
Gallium Ga 1
Germanium Ge 1
Arsenic As 0
Selenium Se 0
Bromine Br 0
Krypton Kr 0
Rubidium Rb 1
X

```

Uses a paste of the element text that I haven't counted in the score. I remove the metal tag (since I'm assuming the compounds are always given with the metal first, so I don't actually need it) and build a dictionary with it. I identify the part to replace with "ide" by checking the end of the string for three letters starting with `i`, four letters ending with `gen`, or otherwise just the last two characters.
> 1 votes

# Answer
# Python, 134 Characters.

```
#T is a string containing the provided information on the elements
from re import*
print sub('(orus|[oy]ge|i?..)$','ide',' '.join(split(r'(\w+) %s '%e,T)[1]for e in findall('[A-Z][a-z]?',raw_input())))

T = """Hydrogen H 0
Helium He 0
Lithium Li 1
Beryllium Be 1
Boron B 0
Carbon C 0
Nitrogen N 0
Oxygen O 0
Fluorine F 0
Neon Ne 0
Sodium Na 1
Magnesium Mg 1
Aluminium Al 1
Silicon Si 0
Phosphorus P 0
Sulfur S 0
Chlorine Cl 0
Argon Ar 0
Potassium K 1
Calcium Ca 1
Scandium Sc 1
Titanium Ti 1
Vanadium V 1
Chromium Cr 1
Manganese Mn 1
Iron Fe 1
Cobalt Co 1
Nickel Ni 1
Copper Cu 1
Zinc Zn 1
Gallium Ga 1
Germanium Ge 1
Arsenic As 0
Selenium Se 0
Bromine Br 0
Krypton Kr 0
Rubidium Rb 1
Strontium Sr 1
Yttrium Y 1
Zirconium Zr 1
Niobium Nb  1
Molybdenum Mo 1
Technetium Tc 1
Ruthenium Ru 1
Rhodium Rh 1
Palladium Pd 1
Silver Ag 1
Cadmium Cd 1
Indium In 1
Tin Sn 1
Antimony Sb 1
Tellurium Te 0
Iodine I 0
Xenon Xe 0
Cesium Cs 1
Barium Ba 1
Lanthanum La 1
Cerium Ce 1
Praseodymium Pr 1
Neodymium Nd 1
Promethium Pm 1
Samarium Sm 1
Europium Eu 1
Gadolinium Gd 1
Terbium Tb 1
Dysprosium Dy 1
Holmium Ho 1
Erbium Er 1
Thulium Tm 1
Ytterbium Yb 1
Lutetium Lu 1
Hafnium Hf 1
Tantalum Ta 1
Tungsten W 1
Rhenium Re 1
Osmium Os 1
Iridium Ir 1
Platinum Pt 1
Gold Au 1
Mercury Hg 1
Thallium Tl 1
Lead Pb 1
Bismuth Bi 1
Polonium Po 1
Astatine At 0
Radon Rn 0
Francium Fr 1
Radium Ra 1
Actinium Ac 1
Thorium Th 1
Protactinium Pa 1
Uranium U 1
Neptunium Np 1
Plutonium Pu 1
Americium Am 1
Curium Cm 1
Berkelium Bk 1
Californium Cf 1
Einsteinium Es 1
Fermium Fm 1
Mendelevium Md 1
Nobelium No 1
Lawrencium Lr 1
Rutherfordium Rf 1
Dubnium Db 1
Seaborgium Sg 1
Bohrium Bh 1
Hassium Hs 1
Meitnerium Mt 1
Darmstadtium Ds 1
Roentgenium Rg 1
Copernicium Cp 1
Ununtrium Uut 0
Flerovium Fl 0
Ununpentium Uup 0
Livermorium Lv 0
Ununseptium Uus 0
Ununoctium Uuo 0"""

```
> 1 votes

# Answer
# Mathematica 252 267 254

**Code**

`ElementData[]` contains information about the elements; it is native to Mathematica.

```
d=ElementData; a=Reverse@SortBy[d[#,"Abbreviation"]&/@d[],StringLength[#]&];
g[e_]:=Row[{e," \[RightArrow] ", p=Row[z=(d[#,"StandardName"] &/@StringCases[e,a]),
  " + " ] , " \[RightArrow] ",p[[1,1]]<> " "<>StringReplace[p[[1,2]],
  f__~~z:"on"|"ogen"|"ygen"|"ine"|"orus"|"ur"|"ic"|"ium":> f~~"ide"] }]

```

---

**Examples**

```
g["NaCl"]
g["K2S"]
g["Yb2P3"]
g["PbTe2"]

```

---

**Explanation**

The code removes digits from the compound, then separates the elements by their abbreviated names. It then converts the abbreviations to the standard names of elements. Finally, it replaces the non-metal by the term with the correct suffix.
> 0 votes

# Answer
## APL ~~142~~ 150

If I am allowed to store the element names and symbols in a pair of nested arrays within the APL workspace then the following code should do it:

```
(e[s⍳c[1]]),((∊¯1×((+/¨⍳¨i)=+/¨(¯1×i)↑¨t⍳¨⊂n)/i←⍴¨t←'ic' 'on' 'ur' 'ine' 'ium' 'ogen' 'ygen' 'orus')↓n←∊e[s⍳(c←(98>⎕av⍳c)⎕penclose c←⍞~⍕⍳9)[2]]),'ide'

```

It works roughly as follows:

```
c←(98>⎕av⍳c)⎕penclose c←⍞~⍕⍳9

```

Takes the input from the screen via ⍞ and splits the chemical name into symbols and discards any numbers

e\[s⍳c\[1\]\]

Looks up the first element name from its symbol. Similarly for c\[2\]

```
(∊¯1×((+/¨⍳¨i)=+/¨(¯1×i)↑¨t⍳¨⊂n)/i←⍴¨t←'ic' 'on' 'ur' 'ine' 'ium' 'ogen' 'ygen' 'orus')↓n

```

Identifies which of the eight possible endings the non-metal has and drops it and then replaces it with ide via:

```
,'ide'

```

There is no error trapping so only works for valid compounds dictated via the one or zero identifier in the list of elements provided.
> 0 votes

---
Tags: code-golf, chemistry
---


title: Interpret whatfuck

text:
# Question
Title: Interpret whatfuck
Smallfuck is a brainfuck-like language with 1-bit cells. It has the following instructions:

```
> Increment the pointer
< Decrement the pointer
* Flip the current bit
[ If the current bit is not set, jump to the instruction after the matching ]
] If the current bit is set, jump to the instruction after the matching [
    ( or just jump unconditionally to matching [ )

```

Whatfuck adds one more instruction:

```
? Nondeterministically set the current bit to 0 or 1.

```

A whatfuck program does not take any input. It can result in one of 3 possibilities: `1` (accept), `0` (reject) or it may never halt.

The program will result in `1` if there exists a sequence of bits chosen for `?`s which results in the program terminating with `1` as the current bit.

The program terminates with `0` if all possible choices terminate with current bit `0`,

If some choices don't terminate, and all choices which terminate do so with `0`, then the program will never terminate.

Your interpreter should run all possibilities simultaneously. You can't try `0` first and then try `1`, because some programs will not terminate when they should. For example, `*[?*]*` will accept with the choice `1`, but never terminate if you always choose `0`.

As an example, here is a python 2 interpreter I wrote, not golfed

## Rules

* Your interpreter must accept a whatfuck program from stdin and print its result.
* You may assume the whatfuck program only contains characters `[]<>*?`
* The array of bits is unbounded on both ends.
* Shortest code wins.

## Some Test Cases

This will fail if your code always tries `0` first

```
*[?*]*
1

```

Is there a subset of `{-7,-3, 5, 8}` whose sum is 3?

```
*<<<<<?[<<<<<<<<<<<<<<]?[<<<<<<]?[>>>>>>>>>>]?[>>>>>>>>>>>>>>>>]<
1

```

Is there a subset of `{-7,-3, 5, 8}` whose sum is 4?

```
*<<<<<<<?[<<<<<<<<<<<<<<]?[<<<<<<]?[>>>>>>>>>>]?[>>>>>>>>>>>>>>>>]<
0

```

Is there a way to assign boolean values to `a`,`b` and `c` such that

`(a XOR b) AND (a XOR c) AND (b XOR c)` is true?

```
?[*>*>*<<]?[*>*>>*<<<]?[*>>*>*<<<]>[*>[*>[*>*<]<]<]>>>
0

```

# Answer
## Python, 305 chars

```
P=raw_input()+'$'
S=[(0,0,[])]
F={}
R={}
i=r=0
for c in P:
 if'['==c:S+=i,
 if']'==c:j=S.pop();F[j]=R[i]=i-j
 i+=1
while S*(1-r):p,t,B=S.pop(0);c=P[p];b=B.count(t)%2;p+=1+F.get(p,0)*(1-b)-R.get(p,0)*b;t+=(c=='>')-(c=='<');B=B+[t]*(c=='*');r|=(c=='$')&b;S+=[(p,t,B)]*(c!='$')+[(p,t,B+[t])]*(c=='?')
print r

```

Keeps track of the nondeterministic set of states in `S`, each with a code position `p`, a tape position `t`, and a list of tape indexes `B`. A tape index can appear multiple times in the list `B`, the tape at that index is 1 if the index appears an odd number of times in `B`.
> 5 votes

# Answer
Infinite tape ahoy!

## Haskell, 516

```
i((p:l,r),(π,'<':φ))=[((l,p:r),('<':π,φ))]
i((l,p:r),(π,'>':φ))=[((p:l,r),('>':π,φ))]
i((l,p:r),(π,'*':φ))=[((l,1-p:r),('*':π,φ))]
i((l,_:r),(π,'?':φ))=[((l,b:r),('?':π,φ))|b<-[0,1]]
i(s@(l,0:r),(π,'[':φ))=[(s,m(']':π,φ)0)]
i(s,(π,'[':φ))=[(s,(']':π,φ))]
i(s,(π,']':φ))=[(s,ξ$m(']':φ,π)0)]
i _=[]
m(l,']':r)0=('[':l,r)
m(l,']':r)n=m('[':l,r)$n-1
m(l,'[':r)n=m(']':l,r)$n+1
m(l,c:r)n=m(c:l,r)n
ν=null;ο=0:ο
μ[]="0"
μ ω|ν[ψ|ψ@((_,b:_),_)<-ω,b>0,ν$i ψ]=μ$ω>>=i
μ _="1"
ξ(a,b)=(b,a)
main=interact$ \ζ->μ[((ο,ο),("",ζ))]

```
> 5 votes

# Answer
## Python (~~405~~ ~~399~~ 379)

It takes the input on one line, but I "may assume the whatfuck program only contains characters `[]<>*?`" and newline isn't on that list :P

```
w,i,p,a={},0,raw_input(),[(0,0,[],[])]
for c in p:
 if c=='[':a+=i,
 if c==']':g=a.pop();w[i],w[g]=g,i
 i+=1
i,z=0,lambda l:l and l.pop()or 0
while a:
 n,c,l,r=a.pop(0)
 try:o=p[n]
 except:
        if c:i=1;break
        continue
 if o=='*':c=not c
 if o=='>':l+=c,;c=z(r)
 if o=='<':r+=c,;c=z(l)
 if o in'[]'and(']'==o)==c:n=w[n]
 if o=='?':a+=(n+1,not c,l[:],r[:]),
 a+=(n+1,c,l,r),
print i

```
> 1 votes

---
Tags: code-golf, interpreter
---


# Question
Title: C: replace AES FIPS-197 SubBytes table by constant-time code
In FIPS-197 (the Advanced Encryption Standard, known as AES), it is made heavy use of `SubBytes`, which could be implemented as

```
unsigned char SubBytes(unsigned char x) {
static const unsigned char t[256] = {
  0x63,0x7C,0x77,0x7B,0xF2,0x6B,0x6F,0xC5,0x30,0x01,0x67,0x2B,0xFE,0xD7,0xAB,0x76,
  0xCA,0x82,0xC9,0x7D,0xFA,0x59,0x47,0xF0,0xAD,0xD4,0xA2,0xAF,0x9C,0xA4,0x72,0xC0,
  0xB7,0xFD,0x93,0x26,0x36,0x3F,0xF7,0xCC,0x34,0xA5,0xE5,0xF1,0x71,0xD8,0x31,0x15,
  0x04,0xC7,0x23,0xC3,0x18,0x96,0x05,0x9A,0x07,0x12,0x80,0xE2,0xEB,0x27,0xB2,0x75,
  0x09,0x83,0x2C,0x1A,0x1B,0x6E,0x5A,0xA0,0x52,0x3B,0xD6,0xB3,0x29,0xE3,0x2F,0x84,
  0x53,0xD1,0x00,0xED,0x20,0xFC,0xB1,0x5B,0x6A,0xCB,0xBE,0x39,0x4A,0x4C,0x58,0xCF,
  0xD0,0xEF,0xAA,0xFB,0x43,0x4D,0x33,0x85,0x45,0xF9,0x02,0x7F,0x50,0x3C,0x9F,0xA8,
  0x51,0xA3,0x40,0x8F,0x92,0x9D,0x38,0xF5,0xBC,0xB6,0xDA,0x21,0x10,0xFF,0xF3,0xD2,
  0xCD,0x0C,0x13,0xEC,0x5F,0x97,0x44,0x17,0xC4,0xA7,0x7E,0x3D,0x64,0x5D,0x19,0x73,
  0x60,0x81,0x4F,0xDC,0x22,0x2A,0x90,0x88,0x46,0xEE,0xB8,0x14,0xDE,0x5E,0x0B,0xDB,
  0xE0,0x32,0x3A,0x0A,0x49,0x06,0x24,0x5C,0xC2,0xD3,0xAC,0x62,0x91,0x95,0xE4,0x79,
  0xE7,0xC8,0x37,0x6D,0x8D,0xD5,0x4E,0xA9,0x6C,0x56,0xF4,0xEA,0x65,0x7A,0xAE,0x08,
  0xBA,0x78,0x25,0x2E,0x1C,0xA6,0xB4,0xC6,0xE8,0xDD,0x74,0x1F,0x4B,0xBD,0x8B,0x8A,
  0x70,0x3E,0xB5,0x66,0x48,0x03,0xF6,0x0E,0x61,0x35,0x57,0xB9,0x86,0xC1,0x1D,0x9E,
  0xE1,0xF8,0x98,0x11,0x69,0xD9,0x8E,0x94,0x9B,0x1E,0x87,0xE9,0xCE,0x55,0x28,0xDF,
  0x8C,0xA1,0x89,0x0D,0xBF,0xE6,0x42,0x68,0x41,0x99,0x2D,0x0F,0xB0,0x54,0xBB,0x16};
return t[x];}

```

This function is not arbitrary; it is a reversible mapping, consisting of an inversion in a Galois Field followed by an affine transformation. All the details are in FIPS-197 section 5.1.1 or here section 4.2.1 (under a slightly different name).

One problem with implementation as a table is that it opens to so-called cache-timing attacks.

Thus your mission is to devise an exact replacement for the above `SubBytes()` function, that exhibits constant-time behavior; we'll assume that's the case when nothing depending on the input `x` of `SubBytes` is used either:

* as an array index,
* as the control operand of `if`, `while`, `for`, `case`, or operator `?:`;
* as any operand of operators `&&`, `||`, `!`, `==`, `!=`, `<`, `>`, `<=`, `>=`, `*`, `/`, `%`;
* as the right operand of operators `>>`, `<<`, `*=`, `/=`, `%=`, `<<=`, `>>=`.

The winning entry will be one with the lowest cost, obtained from the number of operators executed in the input-dependent data path, with a weight of 5 for unary operators `-` and `~` as well as for `<<1`, `>>1`, `+1`, `-1`; weight of 7 for all other operators, shifts with other counts, or adds/subs of other constants (type casts and promotions are free). By principle, that cost is unchanged by unrolling loops (if any), and independent of the input `x`. As a tie-breaker, the answer with the shortest code after removing whitespace and comments wins.

I plan to designate an entry as answer as early as I can in year 2013, UTC. I will consider answers in languages that I've some knowledge of, ranking them as a straight translation to C not optimized for size.

Apologies for the initial omission of `+1` and `-1` in the favored operators, of free casts and promotions, and ranking of size. Note that `*` is prohibited both when unary, and as multiplication.

# Answer
> 14 votes
## Score: 940 933 926 910, field tower approach

```
public class SBox2
{
    public static void main(String[] args)
    {
        for (int i = 0; i < 256; i++) {
            int s = SubBytes(i);
            System.out.format("%02x  ", s);
            if (i % 16 == 15) System.out.println();
        }
    }

    private static int SubBytes(int x) {
        int fwd;
        fwd  = 0x010001 & -(x & 1); x >>= 1; //   7+5+7+5+ | 24+
        fwd ^= 0x1d010f & -(x & 1); x >>= 1; // 7+7+5+7+5+ | 31+
        fwd ^= 0x4f020b & -(x & 1); x >>= 1; // 7+7+5+7+5+ | 31+
        fwd ^= 0x450201 & -(x & 1); x >>= 1; // 7+7+5+7+5+ | 31+
        fwd ^= 0xce080d & -(x & 1); x >>= 1; // 7+7+5+7+5+ | 31+
        fwd ^= 0xa20f0f & -(x & 1); x >>= 1; // 7+7+5+7+5+ | 31+
        fwd ^= 0xc60805 & -(x & 1); x >>= 1; // 7+7+5+7+5+ | 31+
        fwd ^= 0x60070e & -x;                // 7+7+5+     | 19+

        // Running total so far: 229

        int p1;
        {
            int ma = fwd;
            int mb = fwd >> 16;         // 7+         | 7+
            p1  = ma & -(mb&1); ma<<=1; //   7+5+7+5+ | 24+
            p1 ^= ma & -(mb&2); ma<<=1; // 7+7+5+7+5+ | 31+
            p1 ^= ma & -(mb&4); ma<<=1; // 7+7+5+7+5+ | 31+
            p1 ^= ma & -(mb&8);         // 7+7+5+7+   | 26+
            int t = p1 >> 3;            // 7+         | 7+
            p1 ^= (t >> 1) ^ (t & 0xe); // 7+5+7+7+   | 26+
        }

        // Running total so far: 229 + 152 = 381

        int y3, y2, y1, y0;
        {
            int Kinv = (fwd >> 20) ^ p1;     // 7+7+
            int w0 = Kinv & 1; Kinv >>= 1;   // 7+5+
            int w1 = Kinv & 1; Kinv >>= 1;   // 7+5+
            int w2 = Kinv & 1; Kinv >>= 1;   // 7+5+
            int w3 = Kinv & 1;               // 7+

            int t0 = w1 ^ w0 ^ (w2 & w3);      // 7+7+7+
            int t1 = w2 ^ (w0 | w3);           // 7+7+
            int t2 = t0 ^ t1;                  // 7+

            y3 = t2 ^ (t1 & (w1 & w3));        // 7+7+7+
            y2 = t0 ^ (w0 | t2);               // 7+7+
            y1 = w0 ^ w3 ^ (t1 & t0);          // 7+7+7+
            y0 = w3 ^ (t0 | (w1 ^ (w0 | w2))); // 7+7+7+7

        }

        // Running total so far: 381 + 24*7 + 3*5 = 564

        int p2;
        {
            int ma = fwd;
            p2  = ma & -y0; ma<<=1;       //   7+5+5+ | 17+
            p2 ^= ma & -y1; ma<<=1;       // 7+7+5+5+ | 24+
            p2 ^= ma & -y2; ma<<=1;       // 7+7+5+5+ | 24+
            p2 ^= ma & -y3;               // 7+7+5+   | 19+
            int t = p2 >> 3;              // 7+       | 7+
            p2 ^= (t >> 1) ^ (t & 0xe0e); // 7+5+7+7+ | 26
        }

        // Running total so far: 564 + 117 = 681

        int inv8;
        inv8  =  31 & -(p2 & 1);           //   7+5+7+   | 19+
        inv8 ^= 178 & -(p2 & 2); p2 >>= 2; // 7+7+5+7+7+ | 33+
        inv8 ^= 171 & -(p2 & 1);           // 7+7+5+7+   | 26+
        inv8 ^=  54 & -(p2 & 2); p2 >>= 6; // 7+7+5+7+7+ | 33+
        inv8 ^= 188 & -(p2 & 1);           // 7+7+5+7+   | 26+
        inv8 ^=  76 & -(p2 & 2); p2 >>= 2; // 7+7+5+7+7+ | 33+
        inv8 ^= 127 & -(p2 & 1);           // 7+7+5+7+   | 26+
        inv8 ^= 222 & -(p2 & 2);           // 7+7+5+7    | 26+

        return inv8 ^ 0x63;                // 7+         | 7+

        // Grand total: 681 + 229 = 910
    }
}

```

The structure is essentially the same as Boyar and Peralta's implementation - reduce inversion in GF(2^8) to inversion in GF(2^4), break it down into a linear prologue, a non-linear body, and a linear epilogue, and then minimise them separately. I pay some penalties for bit extraction, but I compensate by being able to do operations in parallel (with some judicious padding of the bits of `fwd`). In more detail...

### Background

As mentioned in the problem description, the S-box consists of an inversion in a particular implementation of the Galois field GF(2^8) followed by an affine transformation. If you know what both of those mean, skip this section.

An affine (or linear) transformation is a function `f(x)` which respects `f(x + y) = f(x) + f(y)` and `f(a*x) = a*f(x)`.

A field is a set `F` of elements with two special elements, which we'll call `0` and `1`, and two operators, which we'll call `+` and `*`, which respects various properties. In this section, assume that `x`, `y`, and `z` are elements of `F`.

* The elements of `F` form an abelian group under `+` with `0` as the identity: i.e. `x + y` is an element of `F`; `x + 0 = 0 + x = x`; each `x` has a corresponding `-x` such that `x + (-x) = (-x) + x = 0`; `x + (y + z) = (x + y) + z`; and `x + y` = `y + x`.
* The elements of `F` other than `0` form an abelian group under `*` with `1` as the identity.
* Multiplication distributes over addition: `x * (y + z) = (x * y) + (x * z)`.

It turns out that there are some quite severe limitations on finite fields:

* They must have a number of elements which is a power of a prime.
* They are isomorphic with all other finite fields of the same size (i.e. there's really only one finite field of a given size, and any others are just relabellings; call that field GF(p^k) where `p` is the prime and `k` is the power).
* The multiplicative group `F\{0}` under `*` is cyclic; i.e. there's at least one element `g` such that every element is a power of `g`.
* For powers greater than 1 there is a representation as univariate polynomials of order `k` of the field of the prime order. E.g. GF(2^8) has a representation in terms of polynomials of `x` over GF(2). In fact there's usually more than one representation. Consider `x^7 * x` in GF(2^8); it must be equivalent to some order-7 polynomial, but which? There are a lot of choices which give the right structure; AES chooses to make `x^8 = x^4 + x^3 + x + 1` (the lexicographically smallest polynomial which works).

So how do we compute an inverse in that particular representation of GF(2^8)? It's too chunky a problem to tackle directly, so we need to break it down.

### Field towers: representing GF(2^8) in terms of GF(2^4)

Instead of representing GF(2^8) with polynomials of 8 terms over GF(2) we can represent it with polynomials of 2 terms over GF(2^4). This time we need to choose a linear polynomial for `x^2`. Suppose we choose `x^2 = px + q`. Then `(ax + b) * (cx + d) = (ad + bc + acp)x + (bd + acq)`.

Is it easier to find an inverse in this representation? If `(cx + d) = (ax + b)^-1` we get the simultaneous equations

* `ad + (b + ap)c = 0`
* `bd + (aq)c = 1`

Let `D = [b(b+ap) + a^2 q]` and set `c = a * D^-1`; `d = (b + ap) * D^-1`. So we can do an inverse in GF(2^8) for the cost of a conversion to GF(2^4), an inverse and a few additions and multiplications in GF(2^4), and a conversion back. Even if we do the inverse by means of a table, we've reduced the table size from 256 to 16.

### Implementation details

To construct a representation of GF(4) we can choose between three polynomials to reduce `x^4`:

* `x^4 = x + 1`
* `x^4 = x^3 + 1`
* `x^4 = x^3 + x^2 + x + 1`

The most important difference is in the implementation of multiplication. For any of the three (which correspond to `poly` of 3, 9, f) the following will work:

```
// 14x &, 7x unary -, 3x <<1, 3x >>1, 3x >>3, 6x ^ gives score 226
int mul(int a, int b) {
    // Call current values a = a0, b = b0
    int p = a & -(b & 1);
    a = ((a << 1) ^ (poly & -(a >> 3))) & 15;
    b >>= 1;
    // Now p = a0 * (b0 mod x); a = a0 x; b = b0 div x

    p ^= a & -(b & 1);
    a = ((a << 1) ^ (poly & -(a >> 3))) & 15;
    b >>= 1;
    // Now p = a0 * (b0 mod x^2); a = a0 x^2; b = b0 div x^2

    p ^= a & -(b & 1);
    a = ((a << 1) ^ (poly & -(a >> 3))) & 15;
    b >>= 1;
    // Now p = a0 * (b0 mod x^3); a = a0 x^3; b = b0 div x^3

    p ^= a & -(b & 1);
    // p = a0 * b0

    return p;
}

```

However, if we choose `poly = 3` we can handle the overflow much more efficiently because it has a nice structure: there's no double-overflow, because the two inputs are both cubics and `x^6 = x^2 (x + 1)` is also cubic. In addition we can save the shifts of `b`: since we're leaving the overflow to last, `a0 x^2` doesn't have any set bits corresponding to `x` or 1 and so we can mask it with -4 instead of -1. The result is

```
// 10x &, 4x unary -, 3x <<1, 1x >>1, 1x >>3, 5x ^ gives score 152
int mul(int a, int b) {
    int p;
    p  = a & -(b & 1); a <<= 1;
    p ^= a & -(b & 2); a <<= 1;
    p ^= a & -(b & 4); a <<= 1;
    p ^= a & -(b & 8);
    // Here p = a0 * b0 but with overflow, which we need to bring back down.

    int t = p >> 3;
    p ^= (t >> 1) ^ (t & 0xe);
    return p & 15;
}

```

We still need to choose the values of `p` and `q` for the representation of GF(2^8) over GF(2^4), but we don't have many constraints on them. The one thing that matters is that we can get a linear function from the bits of our original representation to the bits of the working representation. This matters for two reasons: firstly, it's easy to do linear transformations, whereas a non-linear transformation would require optimisation equivalent in difficulty to just optimising the entire S-box; secondly, because we can get some side benefits. To recap the structure:

```
GF256 SubBytes(GF256 x) {
    GF16 a, b, t, D, Dinv, c, d;

    (a, b) = f(x); // f is linear

    t = b + a * p;
    D = b * t + a * a * q;
    Dinv = inverse_GF16(D);
    c = a * Dinv;
    d = t * Dinv;

    return finv(c, d); // finv is also linear
}

```

If the bits of `x` are `x7 x6 ... x0` then since the transform is linear we get `a = f({x7}0000000 + 0{x6}000000 + ... + 0000000{x0}) = f({x7}0000000) + f(0{x6}000000) + ... + f(0000000{x0})`. Square it and we get `a^2 = f({x7}0000000)^2 + f(0{x6}000000)^2 + ... + f(0000000{x0})^2` where the cross-terms cancel (because in GF(2), `1 + 1 = 0`). So `a^2` can also be computed as a linear function of `x`. We can augment the forward linear transform to get:

```
GF256 SubBytes(GF256 x) {
    GF16 a, b, t, a2q, D, Dinv, c, d;

    (a, b, t, a2q) = faug(x);

    D = b * t + a2q;
    Dinv = inverse_GF16(D);
    c = a * Dinv;
    d = t * Dinv;

    return finv(c, d);
}

```

and we're down to three multiplications and one addition. We can also extend the multiplication code to do the two multiplications by `Dinv` in parallel. So our total cost is a forward linear transformation, an addition, two multiplications, an inverse in GF(2^4), and a back linear transformation. We can roll in the post-inverse linear transformation of the S-box and get that essentially for free.

The computation of the coefficients for the linear transformations isn't very interesting, and nor is the micro-optimisation to save a mask here and a shift there. The remaining interesting part is the optimisation of `inverse_GF16`. There are 2^64 different functions from 4 bits to 4 bits, so a direct optimisation requires lots of memory and time. What I've done is to consider 4 functions from 4 bits to 1 bit, place a cap on the total cost permitted for any one function (with a maximum cost of 63 per function I can enumerate all suitable expressions in under a minute), and for each tuple of functions do common subexpression elimination. After 25 minutes of crunching, I find that the best inverse possible with that cap has a total cost of 133 (an average of 33.25 per bit of the output, which isn't bad considering that the cheapest expression for any individual bit is 35).

I'm still experimenting with other approaches to minimise the inversion in GF(2^4), and an approach which builds bottom-up rather than top-down has yielded an improvement from 133 to 126.

# Answer
> 8 votes
## **Score: 980=7\*5+115\*7+7\*5+15\*7, Boyar and Peralta's minimization**

I found *A new combinational logic minimization technique with applications to cryptology* by Joan Boyar and René Peralta, which (save for the C formalism) does what's required. The technique used to derive their equations is patented by no less than the USA. I just did a straight C translation of their equations, kindly linked here.

```
unsigned char SubBytes_Boyar_Peralta(unsigned char x7){
  unsigned char
  x6=x7>>1,x5=x6>>1,x4=x5>>1,x3=x4>>1,x2=x3>>1,x1=x2>>1,x0=x1>>1,
  y14=x3^x5,y13=x0^x6,y9=x0^x3,y8=x0^x5,t0=x1^x2,y1=t0^x7,y4=y1^x3,y12=y13^y14,y2=y1^x0,
  y5=y1^x6,y3=y5^y8,t1=x4^y12,y15=t1^x5,y20=t1^x1,y6=y15^x7,y10=y15^t0,y11=y20^y9,y7=x7^y11,
  y17=y10^y11,y19=y10^y8,y16=t0^y11,y21=y13^y16,y18=x0^y16,t2=y12&y15,t3=y3&y6,t4=t3^t2,
  t5=y4&x7,t6=t5^t2,t7=y13&y16,t8=y5&y1,t9=t8^t7,t10=y2&y7,t11=t10^t7,t12=y9&y11,
  t13=y14&y17,t14=t13^t12,t15=y8&y10,t16=t15^t12,t17=t4^t14,t18=t6^t16,t19=t9^t14,
  t20=t11^t16,t21=t17^y20,t22=t18^y19,t23=t19^y21,t24=t20^y18,t25=t21^t22,t26=t21&t23,
  t27=t24^t26,t28=t25&t27,t29=t28^t22,t30=t23^t24,t31=t22^t26,t32=t31&t30,t33=t32^t24,
  t34=t23^t33,t35=t27^t33,t36=t24&t35,t37=t36^t34,t38=t27^t36,t39=t29&t38,t40=t25^t39,
  t41=t40^t37,t42=t29^t33,t43=t29^t40,t44=t33^t37,t45=t42^t41,z0=t44&y15,z1=t37&y6,
  z2=t33&x7,z3=t43&y16,z4=t40&y1,z5=t29&y7,z6=t42&y11,z7=t45&y17,z8=t41&y10,z9=t44&y12,
  z10=t37&y3,z11=t33&y4,z12=t43&y13,z13=t40&y5,z14=t29&y2,z15=t42&y9,z16=t45&y14,z17=t41&y8,
  t46=z15^z16,t47=z10^z11,t48=z5^z13,t49=z9^z10,t50=z2^z12,t51=z2^z5,t52=z7^z8,t53=z0^z3,
  t54=z6^z7,t55=z16^z17,t56=z12^t48,t57=t50^t53,t58=z4^t46,t59=z3^t54,t60=t46^t57,
  t61=z14^t57,t62=t52^t58,t63=t49^t58,t64=z4^t59,t65=t61^t62,t66=z1^t63,s0=t59^t63,
  s6=t56^t62,s7=t48^t60,t67=t64^t65,s3=t53^t66,s4=t51^t66,s5=t47^t65,s1=t64^s3,s2=t55^t67;
  return (((((((s0<<1|s1&1)<<1|s2&1)<<1|s3&1)<<1|s4&1)<<1|s5&1)<<1|s6&1)<<1|s7&1)^0x63;}

```

# Answer
> 5 votes
## Score: 10965

This uses the same principle of unrolling the array lookup. May require extra casts.

Thanks to ugoren for pointing out how to improve `is_zero`.

```
// Cost: 255 * (5+7+24+7) = 10965
unsigned char SubBytes(unsigned char x) {
    unsigned char r = 0x63;
    char c = (char)x;
    c--; r ^= is_zero(c) & (0x63^0x7c); // 5+7+24+7 inlining the final xor
    c--; r ^= is_zero(c) & (0x63^0x77); // 5+7+24+7
    // ...
    c--; r ^= is_zero(c) & (0x63^0x16); // 5+7+24+7
    return r;
}

// Cost: 24
// Returns (unsigned char)-1 when input is 0 and 0 otherwise
unsigned char is_zero(char c) {
    // Shifting a signed number right is unspecified, so use unsigned
    unsigned char u;
    c |= -c;               // 7+5+
    u = (unsigned char)c;
    u >>= (CHAR_BITS - 1); // 7+
    c = (char)u;
    // c is 0 if we want -1 and 1 otherwise.
    c--;                   // 5
    return (unsigned char)c;
}

```

# Answer
> 3 votes
## Score: 9109, algebraic approach

I'll leave the lookup approach in case anyone can improve it drastically, but it turns out that a good algebraic approach is possible. This implementation finds the multiplicative inverse using Euclid's algorithm. I've written it in Java but in principle it can be ported to C - I've commented the parts which would change if you want to rework it using only 8-bit types.

Thanks to ugoren for pointing out how to shorten the `is_nonzero` check in a comment on my other answer.

```
public class SBox
{
    public static void main(String[] args)
    {
        for (int i = 0; i < 256; i++) {
            int s = SubBytes(i);
            System.out.format("%02x  ", s);
            if (i % 16 == 15) System.out.println();
        }
    }

    // Total cost: 9109
    public static int SubBytes(int x)
    {
        x = inv_euclid(x); // 9041
        x = affine(x);     // 68
        return x;
    }

    // Total cost: 68
    private static int affine(int s0) {
        int s = s0;
        s ^= (s0 << 1) ^ (s0 >> 7); // 5 + 7
        s ^= (s0 << 2) ^ (s0 >> 6); // 7 + 7
        s ^= (s0 << 3) ^ (s0 >> 5); // 7 + 7
        s ^= (s0 << 4) ^ (s0 >> 4); // 7 + 7
        return (s ^ 0x63) & 0xff;   // 7 + 7
    }

    // Does the inverse in the Galois field for a total cost of 24 + 9010 + 7 = 9041
    private static int inv_euclid(int s) {
        // The first part of handling the special case: cost of 24
        int zeromask = is_nonzero(s);

        // NB the special value of r would complicate the unrolling slightly with unsigned bytes
        int r = 0x11b, a = 0, b = 1;

        // Total cost of loop: 7*(29+233+566+503+28) - 503 = 9010
        for (int depth = 0; depth < 7; depth++) { // 7*(
            // Calculate mask to fake out when we're looping further than necessary: cost 29
            int mask = is_nonzero(s >> 1);

            // Cost: 233
            int ord = polynomial_order(s);

            // This next block does div/rem at a total cost of 6*(24+49) + 69 + 59 = 566
            int quot = 0, rem = r;
            for (int i = 7; i > 1; i--) {                   // 6*(
                int divmask = is_nonzero(ord & (rem >> i)); // 24+7+7
                quot ^= (1 << i) & divmask;                 // 7+0+7+ since 1<<i is inlined on unrolling
                rem ^= (s << i) & divmask;                  // 7+7+7) +
            }
            int divmask1 = is_nonzero(ord & (rem >> 1));    // 24+7+5
            quot ^= 2 & divmask1;                           // 7+7+
            rem ^= (s << 1) & divmask1;                     // 7+5+7+
            int divmask0 = is_nonzero(ord & rem);           // 24+7
            quot ^= 1 & divmask0;                           // 7+7+
            rem ^= s & divmask0;                            // 7+7

            // This next block does the rest for the cost of a mul (503) plus 28
            // When depth = 0, b = 1 so we can skip the mul on unrolling
            r = s;
            s = rem;
            quot = mul(quot, b) ^ a;
            a = b;
            b ^= (quot ^ b) & mask;
        }

        // The rest of handling the special case: cost 7
        return b & zeromask;
    }

    // Gets the highest set bit in the input. Assumes that it's always at least 1<<1
    // Cost: 233
    private static int polynomial_order(int s) {
        int ord = 2;
        ord ^= 6 & -((s >> 2) & 1);           // 7+7+5+7+7 = 33 +
        ord ^= (ord ^ 8) & -((s >> 3) & 1);   // 7+7+7+5+7+7 = 40 +
        ord ^= (ord ^ 16) & -((s >> 4) & 1);  // 40 +
        ord ^= (ord ^ 32) & -((s >> 5) & 1);  // 40 +
        ord ^= (ord ^ 64) & -((s >> 6) & 1);  // 40 +
        ord ^= (ord ^ 128) & -((s >> 7) & 1); // 40
        return ord;
    }

    // Returns 0 if c is 0 and -1 otherwise
    // Cost: 24
    private static int is_nonzero(int c) {
        c |= -c;   // 7+5+
        c >>>= 31; // 7+ (simulating a cast to unsigned and right shift by CHAR_BIT)
        c = -c;    // 5+ (could be saved assuming a particular implementation of signed right shift)
        return c;
    }

    // Performs a multiplication in the Rijndael finite field
    // Cost: 503 (496 if working with unsigned bytes)
    private static int mul(int a, int b) {
        int p = 0;
        for (int counter = 0; counter < 8; counter++) { // 8*(_+_
            p ^= a & -(b & 1);                          // +7+7+5+7
            a = (a << 1) ^ (0x1b & -(a >> 7));          // +5+7+7+5+7
            b >>= 1;                                    // +5)
        }
        p &= 0xff;                                      // +7 avoidable with unsigned bytes
        return p;
    }
}

```

# Answer
> 2 votes
## **Score: 256\*(7+(8\*(7+7+7)-(2+2))+5+7+7)=48640 (assuming loops unrolled)**

```
unsigned char SubBytes(unsigned char x) {
static const unsigned char t[256] = {
  0x63,0x7C,0x77,0x7B,0xF2,0x6B,0x6F,0xC5,0x30,0x01,0x67,0x2B,0xFE,0xD7,0xAB,0x76,
  0xCA,0x82,0xC9,0x7D,0xFA,0x59,0x47,0xF0,0xAD,0xD4,0xA2,0xAF,0x9C,0xA4,0x72,0xC0,
  0xB7,0xFD,0x93,0x26,0x36,0x3F,0xF7,0xCC,0x34,0xA5,0xE5,0xF1,0x71,0xD8,0x31,0x15,
  0x04,0xC7,0x23,0xC3,0x18,0x96,0x05,0x9A,0x07,0x12,0x80,0xE2,0xEB,0x27,0xB2,0x75,
  0x09,0x83,0x2C,0x1A,0x1B,0x6E,0x5A,0xA0,0x52,0x3B,0xD6,0xB3,0x29,0xE3,0x2F,0x84,
  0x53,0xD1,0x00,0xED,0x20,0xFC,0xB1,0x5B,0x6A,0xCB,0xBE,0x39,0x4A,0x4C,0x58,0xCF,
  0xD0,0xEF,0xAA,0xFB,0x43,0x4D,0x33,0x85,0x45,0xF9,0x02,0x7F,0x50,0x3C,0x9F,0xA8,
  0x51,0xA3,0x40,0x8F,0x92,0x9D,0x38,0xF5,0xBC,0xB6,0xDA,0x21,0x10,0xFF,0xF3,0xD2,
  0xCD,0x0C,0x13,0xEC,0x5F,0x97,0x44,0x17,0xC4,0xA7,0x7E,0x3D,0x64,0x5D,0x19,0x73,
  0x60,0x81,0x4F,0xDC,0x22,0x2A,0x90,0x88,0x46,0xEE,0xB8,0x14,0xDE,0x5E,0x0B,0xDB,
  0xE0,0x32,0x3A,0x0A,0x49,0x06,0x24,0x5C,0xC2,0xD3,0xAC,0x62,0x91,0x95,0xE4,0x79,
  0xE7,0xC8,0x37,0x6D,0x8D,0xD5,0x4E,0xA9,0x6C,0x56,0xF4,0xEA,0x65,0x7A,0xAE,0x08,
  0xBA,0x78,0x25,0x2E,0x1C,0xA6,0xB4,0xC6,0xE8,0xDD,0x74,0x1F,0x4B,0xBD,0x8B,0x8A,
  0x70,0x3E,0xB5,0x66,0x48,0x03,0xF6,0x0E,0x61,0x35,0x57,0xB9,0x86,0xC1,0x1D,0x9E,
  0xE1,0xF8,0x98,0x11,0x69,0xD9,0x8E,0x94,0x9B,0x1E,0x87,0xE9,0xCE,0x55,0x28,0xDF,
  0x8C,0xA1,0x89,0x0D,0xBF,0xE6,0x42,0x68,0x41,0x99,0x2D,0x0F,0xB0,0x54,0xBB,0x16};

unsigned char ret_val = 0;
int i,j;
for(i=0;i<256;i++) {
  unsigned char is_index = (x ^ ((unsigned char) i));
  for(j=0;j<8;j++) {
   is_index |= (is_index << (1 << j)) | (is_index >> (1 << j));
  }
  is_index = ~is_index;
  ret_val |= is_index & t[i];
}

return ret_val;}

```

Explanation:

Essentially an array lookup reimplemented using bitwise operators and always processing the entire array. We loop through the array, and xor `x` with each index, then use bitwise operators to logically negate the result, so we get 255 when `x=i` and 0 otherwise. We bitwise-and this with the array-value, so that the chosen value is unchanged and the others become 0. Then we take the bitwise-or of this array, thereby pulling out only the chosen value.

The two `1 << j` operations would go away as part of unrolling the loop, replacing them with the powers of 2 from 1 through 128.

# Answer
> 0 votes
## Score 1968 1692, using the lookup table

**Note: This solution doesn't pass the criteria, because of `w >> b`.**

Using the lookup table, but reading 8 bytes at a time.
3\*7 + 32 * (6\*7 + 2\*5) + 7 = 692

```
unsigned char SubBytes(unsigned char x){

static const unsigned char t[256] = {
  0x63,0x7C,0x77,0x7B,0xF2,0x6B,0x6F,0xC5,0x30,0x01,0x67,0x2B,0xFE,0xD7,0xAB,0x76,
  0xCA,0x82,0xC9,0x7D,0xFA,0x59,0x47,0xF0,0xAD,0xD4,0xA2,0xAF,0x9C,0xA4,0x72,0xC0,
  0xB7,0xFD,0x93,0x26,0x36,0x3F,0xF7,0xCC,0x34,0xA5,0xE5,0xF1,0x71,0xD8,0x31,0x15,
  0x04,0xC7,0x23,0xC3,0x18,0x96,0x05,0x9A,0x07,0x12,0x80,0xE2,0xEB,0x27,0xB2,0x75,
  0x09,0x83,0x2C,0x1A,0x1B,0x6E,0x5A,0xA0,0x52,0x3B,0xD6,0xB3,0x29,0xE3,0x2F,0x84,
  0x53,0xD1,0x00,0xED,0x20,0xFC,0xB1,0x5B,0x6A,0xCB,0xBE,0x39,0x4A,0x4C,0x58,0xCF,
  0xD0,0xEF,0xAA,0xFB,0x43,0x4D,0x33,0x85,0x45,0xF9,0x02,0x7F,0x50,0x3C,0x9F,0xA8,
  0x51,0xA3,0x40,0x8F,0x92,0x9D,0x38,0xF5,0xBC,0xB6,0xDA,0x21,0x10,0xFF,0xF3,0xD2,
  0xCD,0x0C,0x13,0xEC,0x5F,0x97,0x44,0x17,0xC4,0xA7,0x7E,0x3D,0x64,0x5D,0x19,0x73,
  0x60,0x81,0x4F,0xDC,0x22,0x2A,0x90,0x88,0x46,0xEE,0xB8,0x14,0xDE,0x5E,0x0B,0xDB,
  0xE0,0x32,0x3A,0x0A,0x49,0x06,0x24,0x5C,0xC2,0xD3,0xAC,0x62,0x91,0x95,0xE4,0x79,
  0xE7,0xC8,0x37,0x6D,0x8D,0xD5,0x4E,0xA9,0x6C,0x56,0xF4,0xEA,0x65,0x7A,0xAE,0x08,
  0xBA,0x78,0x25,0x2E,0x1C,0xA6,0xB4,0xC6,0xE8,0xDD,0x74,0x1F,0x4B,0xBD,0x8B,0x8A,
  0x70,0x3E,0xB5,0x66,0x48,0x03,0xF6,0x0E,0x61,0x35,0x57,0xB9,0x86,0xC1,0x1D,0x9E,
  0xE1,0xF8,0x98,0x11,0x69,0xD9,0x8E,0x94,0x9B,0x1E,0x87,0xE9,0xCE,0x55,0x28,0xDF,
  0x8C,0xA1,0x89,0x0D,0xBF,0xE6,0x42,0x68,0x41,0x99,0x2D,0x0F,0xB0,0x54,0xBB,0x16};

  unsigned long long *t2 = (unsigned long long *)t;
  int a = x>>3, b=(x&7)<<3;                       // 7+7+7
  int i;
  int ret = 0;
  for (i=0;i<256/8;i++) {                         // 32 *
      unsigned long long w = t2[i];
      int badi = ((unsigned int)(a|-a))>>31;      // 7+7+5
      w &= (badi-1);                              // +7+7
      a--;                                        // +5
      ret |= w >> b;                              // +7+7
  }
  return ret & 0xff;                              // +7
}

```

# Answer
> 0 votes
## Table lookup and mask, score = 256 * (5\*7+1\*5) = 10240

Uses table lookup with a mask to pick out only the result we want. Uses the fact that `j|-j` is either negative (when i!=x) or zero (when i==x). Shifting makes an all-one or all-zero mask which is used to select out only the entry we want.

```
static const unsigned char t[256] = {
  0x63,0x7C,0x77,0x7B,0xF2,0x6B,0x6F,0xC5,0x30,0x01,0x67,0x2B,0xFE,0xD7,0xAB,0x76,
  0xCA,0x82,0xC9,0x7D,0xFA,0x59,0x47,0xF0,0xAD,0xD4,0xA2,0xAF,0x9C,0xA4,0x72,0xC0,
  0xB7,0xFD,0x93,0x26,0x36,0x3F,0xF7,0xCC,0x34,0xA5,0xE5,0xF1,0x71,0xD8,0x31,0x15,
  0x04,0xC7,0x23,0xC3,0x18,0x96,0x05,0x9A,0x07,0x12,0x80,0xE2,0xEB,0x27,0xB2,0x75,
  0x09,0x83,0x2C,0x1A,0x1B,0x6E,0x5A,0xA0,0x52,0x3B,0xD6,0xB3,0x29,0xE3,0x2F,0x84,
  0x53,0xD1,0x00,0xED,0x20,0xFC,0xB1,0x5B,0x6A,0xCB,0xBE,0x39,0x4A,0x4C,0x58,0xCF,
  0xD0,0xEF,0xAA,0xFB,0x43,0x4D,0x33,0x85,0x45,0xF9,0x02,0x7F,0x50,0x3C,0x9F,0xA8,
  0x51,0xA3,0x40,0x8F,0x92,0x9D,0x38,0xF5,0xBC,0xB6,0xDA,0x21,0x10,0xFF,0xF3,0xD2,
  0xCD,0x0C,0x13,0xEC,0x5F,0x97,0x44,0x17,0xC4,0xA7,0x7E,0x3D,0x64,0x5D,0x19,0x73,
  0x60,0x81,0x4F,0xDC,0x22,0x2A,0x90,0x88,0x46,0xEE,0xB8,0x14,0xDE,0x5E,0x0B,0xDB,
  0xE0,0x32,0x3A,0x0A,0x49,0x06,0x24,0x5C,0xC2,0xD3,0xAC,0x62,0x91,0x95,0xE4,0x79,
  0xE7,0xC8,0x37,0x6D,0x8D,0xD5,0x4E,0xA9,0x6C,0x56,0xF4,0xEA,0x65,0x7A,0xAE,0x08,
  0xBA,0x78,0x25,0x2E,0x1C,0xA6,0xB4,0xC6,0xE8,0xDD,0x74,0x1F,0x4B,0xBD,0x8B,0x8A,
  0x70,0x3E,0xB5,0x66,0x48,0x03,0xF6,0x0E,0x61,0x35,0x57,0xB9,0x86,0xC1,0x1D,0x9E,
  0xE1,0xF8,0x98,0x11,0x69,0xD9,0x8E,0x94,0x9B,0x1E,0x87,0xE9,0xCE,0x55,0x28,0xDF,
  0x8C,0xA1,0x89,0x0D,0xBF,0xE6,0x42,0x68,0x41,0x99,0x2D,0x0F,0xB0,0x54,0xBB,0x16};

unsigned char SubBytes(unsigned char x) {
  unsigned char r = 255;
  for (int i = 0; i < 256; i++) {
    int j = i - x;
    r &= t[i] | ((j | -j) >> 31);
  }
  return r;
}

```

---
Tags: code-challenge, c, cryptography
---


title: "First time" test

text:
# Question
Title: "First time" test
What is the shortest C expression that is defined to evaluated to false the first time and true for every time after that:

Reference implementation:

```
bool b = false;  // you get this for free.

(b ? true : b = true, false)  // only this line is measured.

```

# Answer
### 3 chars:

As Keith Randall suggested in a comment, if we can use floats or doubles, this should do the trick:

```
float b = 0;  // free

b++

```

Eventually, as `b` is incremented repeatedly, two things may happen: either the addition overflows (and thus evaluates to `HUGE_VAL`, which may be infinite or a large positive value) or, more likely, the roundoff step size simply grows larger than one, turning the increment into a no-op. In either case, the expression should continue to evaluate as true.
> 11 votes

# Answer
**6 characters**

```
int i = 0; //free
i||i++

```

OTOH: I like Peter Taylor's solution as it has no branch so it may be faster (depending on compiler details).

p.s. I came up with that after posting the question (honest!).
> 10 votes

# Answer
With:

```
long long b = 0;

```

then three characters are enough for many applications:

```
b++

```

Evaluates false first and true for a long time thereafter ;-)
> 8 votes

# Answer
**7 characters**

As Peter Taylor suggested, still `int a = 2;`

```
!(a/=2)

```

**8 characters (old)**

Start with `int a = 2;`

```
!(a>>=1)

```

Another version of this: `int b = 0x40000000;`

```
!(b<<=1)

```
> 7 votes

# Answer
## 9 chars:

```
b=0;//free
(b&(b=1))

```

at least if it's valid c (not undefined behavior)

## 12 chars

```
(b?b:!(b=1))

```

this is valid c
> 2 votes

# Answer
### ~~11~~ 10 chars

I can't beat the three char approach, but make it different:

```
int b = 0;  // free

b?b:0*(b=1) // 11 characters
b||0*(b=1)  // one character less thanks to breadbox

```
> 1 votes

# Answer
```
int b=1; // for free
!b|(b=0)

```

bit-wise or works as well since in first trial `0|0` yields 0 and in other trials `!0|0` yields `!0` which is guaranteed to be true. It is also ANSI-compliant, I've tried the following code with GCC 4.6.1 with `-ansi` flag:

```
#include <stdio.h>
main () {
  int b=1, i=0;
  for (;i<5;++i)
    printf ("%d",!b|(b=0));
}

```
> 1 votes

# Answer
## APL (5 or 6)

If I'm only allowed to initialize the variable to 0, it's 6 characters:

```
A←0    ⍝ free
⊃A←⍴⍴A

```

How it works: `⍴A` is the size of A (which is the empty list the first time around, because `0` is a scalar), so `⍴⍴A` is the size of the size of A (which is `[0]` the first time, because a one-dimensional empty list has zero values in one dimension). This is then assigned to A (`A←`) and the first element is returned ().

1. `A` is `0`, `⍴A` is `[]`, then `A` is set to `⍴⍴A` which is `[0]`, and the first element is returned (`0`).
2. `A` is `[0]`, `⍴A` is `[1]`, then `A` is set to `⍴⍴A` which is `[1]`, and the first element is returned (`1`).
3. `A` is `[1]`, so `⍴A` remains `[1]`, so `A` is set to `⍴⍴A` which remains `[1]` and it returns `1`.

If I'm allowed to initialise the variable to anything I want, I can set it to the empty list and drop one of the s to make it 5 characters:

```
A←⍬    ⍝ free, set to empty list
⊃A←⍴A

```
> 1 votes

# Answer
**9 chars**

```
b=1; //free
!b||(b=0)

```

*edited: no longer undefined behavior*
> 0 votes

# Answer
```
bool b = false; // for free?
b = b?b:!b;

```
> 0 votes

# Answer
What about this:

```
bool b = false;

!b+b++

```
> 0 votes

# Answer
# 1 Character

Since you didn't specify which compiler and/or which command line options are to be used, here's my 1 character solution:

```
bool b = false;

X

```

Compile with

```
gcc -DX='(b ? true : b = true, false)'

```
> -3 votes

---
Tags: code-golf, decision-problem, tips, c
---


# Question
Title: Gregorian to Noxu Time System Conversion
The world's changing to a new time system! We need to update our computer programs. Given an input of epoch time (number of seconds since January 1st, 1970 00:00), print out a time in the new Noxu date-time format.

864 seconds make one Fluffster. 100 Fluffsters make a Skizzle. There are 4 Skizzles in one Zestpond. Their names are Looplab, Sevit, Hexteria, and Sinpad. There are 91 Zestponds in one Lulerain.

The format is Lulerain Zestpond-Skizzle-Fluffster. Fluffsters are rounded to two decimal places. An example would be `50 13-Sevit-40.90`.

Given that epoch 0 was `0 0-Looplab-00.00`, create a program that takes input either via stdin or as a command line argument of any epoch time between 0 and 2^32, and prints out the Noxu equivalent.

### Time of edit:

```
1357510372 -> 43 14-Sinpad-92.56

```

### Random test data:

```
675416077 -> 21 43-Sevit-31.57
330585453 -> 10 46-Hexteria-22.05
1328127085 -> 42 20-Sinpad-84.13
837779784 -> 26 58-Looplab-52.53
1240280676 -> 39 39-Sinpad-10.04
122646385 -> 3 81-Sinpad-51.83
1311245658 -> 41 63-Looplab-45.44
57792972 -> 1 76-Looplab-90.01
788388068 -> 25 6-Looplab-86.19
304341865 -> 9 61-Hexteria-47.53
417857784 -> 13 26-Looplab-31.69
671276878 -> 21 31-Sevit-40.83
1259758896 -> 40 5-Looplab-54.28
604286664 -> 19 19-Hexteria-5.86
646395018 -> 20 50-Sevit-42.38
563025133 -> 17 82-Looplab-49.46
96133144 -> 3 5-Looplab-65.21
101542552 -> 3 20-Sinpad-26.10
1006825856 -> 32 1-Sevit-7.70
928867348 -> 29 48-Hexteria-77.95
1235022079 -> 39 24-Hexteria-23.70
439505287 -> 13 88-Hexteria-86.67
99686711 -> 3 15-Sevit-78.14
379859609 -> 12 7-Looplab-52.33
1167091685 -> 37 10-Looplab-0.56
612032437 -> 19 41-Sinpad-70.88
503040778 -> 15 90-Hexteria-23.12
1084809411 -> 34 44-Sinpad-66.45
1105664386 -> 35 14-Sevit-4.15
197303893 -> 6 24-Sinpad-60.99
368559287 -> 11 65-Sevit-73.25
686824300 -> 21 76-Sevit-35.53
196468204 -> 6 22-Sevit-93.75
673542185 -> 21 37-Sinpad-62.71
993063782 -> 31 52-Sevit-79.38
270951743 -> 8 56-Looplab-1.55
1074506753 -> 34 15-Looplab-42.08
198143696 -> 6 27-Sevit-32.98
539601298 -> 17 14-Sevit-38.54
110090607 -> 3 45-Hexteria-19.68
276492708 -> 8 72-Looplab-14.71
113389138 -> 3 55-Looplab-37.43
571578220 -> 18 15-Sinpad-48.87
1238516450 -> 39 34-Hexteria-68.11
742293312 -> 23 54-Sinpad-35.78
1031929490 -> 32 73-Sinpad-62.84
503091914 -> 15 90-Hexteria-82.31
264094386 -> 8 36-Looplab-64.80
483820698 -> 15 34-Sinpad-77.66
548410387 -> 17 39-Sinpad-34.24

```

# Answer
> 2 votes
# dc - 81

```
2k864/0k100~[Looplab]0:a[Sevit]1:a[Hexteria]2:a[Sinpad]3:ar4~;ar91~rn32Pn45dPrnPp

```

Expects the epoch time already on the stack so invoke as, e.g.

```
dc -e `date +%s` -e '2k864/0k100~[Looplab]0:a[Sevit]1:a[Hexteria]2:a[Sinpad]3:ar4~;ar91~rn32Pn45dPrnPp'

```

to get the current Noxu time or add one character to accept the time from stdin

```
?2k864/0k100~[Looplab]0:a[Sevit]1:a[Hexteria]2:a[Sinpad]3:ar4~;ar91~rn32Pn45dPrnPp

```

## annotated version

```
2 k             # set the precision to 2 decimal places
864 /           # divide the number of seconds by 864 to get fluffsters
0 k             # set the precision back to 0 decimal places
100 ~           # divrem by 100; fluffsters are at the top skizzles under it
[Looplab] 0 :a  # set a[0] to the string Looplab
[Sevit] 1 :a    # set a[1] to Sevit
[Hexteria] 2 :a # set a[2] to Hexteria
[Sinpad] 3 :a   # set a[3] to Sinpad
r               # swap fluffsters and skizzles on the stack
4 ~             # divrem the skizzles by 4; skizzles on top zestpond under it
;a              # use the skizzle as an index into a
r               # swap the skizzle string and zestponds
91 ~            # divrem the zestponds by 91; zestponds on top lulerain under
r               # swap zestponds and lulerains
# now the stack has (from top to bottom)
# lulerains
# zestponds
# skizzle (as the name)
# fluffster
n               # pop and print the lulerains (without a newline)
32 P            # print a space character
n               # pop and print the zestponds
45 d P          # print a - and leave 45 on the top of the stack
r               # swap the 45 and the skizzle name
n               # pop and print the skizzle name
P               # print a - from the 45 that was on the stack
p               # finally print the fluffster (with a newline)

```

When the number of fluffsters is less than 1 there is no leading zero printed, to get the leading zero, it is

```
2k864/0k100~[Looplab]0:a[Sevit]1:a[Hexteria]2:a[Sinpad]3:ar4~;ar91~rn32Pn45dPrnPd[0n]sb1>bp

```

at a cost of 10 extra characters (`d[0n]sb1>b`)

# Answer
> 4 votes
# APL, 87

```
t[3]←(1+3⌷t←137 91 4 100⊤⍎2⍕⎕÷864)⌷'Looplab' 'Sevit' 'Hexteria' 'Sinpad'
'  '⎕R'-'⍕t

```

APL has an advantage in these time system conversion challenges due to the built-in encode function, at the cost of expensive string manipuation

**Explanation**
(using `1357510372` as example)

`⎕÷864` takes user input from screen, divide by 864 (`1571192.56018519`)
`⍎2⍕` and round to 2 dp. (`1571192.56`)
`137 91 4 100⊤` Then, converts to Noxu Time System (`43 14 3 92.56`)
`t←` and assign that to variable `t`.
`1+3⌷` take the 3rd item from `t`, add 1 to account for 1-based indexing, (`4`)
`(`...`)⌷'Looplab' 'Sevit' 'Hexteria' 'Sinpad'` convert to Skizzle name, (`Sinpad`)
`t[3]←` and finally plug back into the 3rd item of `t`.

`⍕t` Convert `t` to a string representation, (`43 14  Sinpad  92.56`)
`' '⎕R'-'` and replaces 2 spaces with a dash (`43 14-Sinpad-92.56`)

# Answer
> 2 votes
## Mathematica 152

Still has some format issues. Spaces added for clarity

```
Flatten@{#[[5]], {Looplab, Sevit, Hexteria,  Sinpad}[[#[[4, 2]] + 1]],
        N[#[[3, 2]] + #[[2, 2]]/864, 4]} &@
               FoldList[QuotientRemainder[#1[[1]], #2] &, {#, 0}, {864, 100, 4, 91}]&

```

# Answer
> 2 votes
## Python, 123

```
x=input()
b=86400
c=b*4
d=c*91
print x/d,'%d-%s-%.2f'%(x%d/c,['Looplab','Sevit','Hexteria','Sinpad'][x%d%c/b],x%d%c%b/864.)

```

# Answer
> 2 votes
## **Ruby, ~~114~~ 112**

```
x=gets.to_f
puts'%d %d-%s-%.2f'%[x/d=91*c=4*b=86400,(x%=d)/c,%w[Looplab Sevit Hexteria Sinpad][x%c/b],x%c%b/864]

```

Meh. Basically grc's solution but with inline assignments.

Edit: Saved 2 chars by changing `to_i` to `to_f` so I don't need the float literal later.

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


# Question
Title: Write the implementation to pass this test
Given the following test, implement an `addOne` function in C# so it passes, without any modification to the test. TIP: Yes, it is possible.

```
[TestMethod]
public void TheChallenge()
{
    int a = 1;

    addOne(a);

    Assert.IsTrue(a == 2);
}

```

**EDIT:** clarified the Assert to avoid confusion. The value of `a` should be 2; there's no trick there.

# Answer
> 14 votes
Ummm, simply provide an implementation of AssertTrue that doesn't throw anything?

```
void addOne(int a){}

void AssertTrue(bool b) { }

```

You never specified what testing framework is used here. It looks like MSTest, but I fired up a new test project and AssertTrue doesn't exist, so I took the liberty of implementing it myself.

# EDIT

This solution might be what you were fishing for:

```
void addOne(int x)
{
  unsafe
  {
    int* i = &x;
    i += 4;
    *i += 1;
  }
}

```

I feels pretty fragile, but it works on my box consistently. It probably depends heavily on the compiler, so hopefully it is reproducible elsewhere.

---
Tags: c#, programming-puzzle
---


title: Identify the compiler

text:
# Question
Title: Identify the compiler
**The challenge**
You are given a function `compile(s: String): Integer` which returns `0` if `s` could be compiled and anything other than `0` if it failed (the resulting code is not important).

The thing is that you don't know for what language the function is made for, so it is up to you to figure that out by giving the function small snippets of code and observing what it returns. The good part is that a team of scientists have tried before you and have narrowed down the list to **C, C++, C#, Java and JavaScript** (these are the only widespread languages which have similar syntax I could think of).

**Rules**

* General code-golf rules apply.
* There is no strict output format; as long as it's readable and understandable it's ok.
* If these 5 languages are not enough for you then you can add your own favourites and you'll be rewarded with extra stars (★) (that do nothing).

Note1: the compiler is up to date with the latest standard of whatever language it's designed for.
Note2: I know JavaScript does not *compile*, but it goes though some parsing process; if it's valid JavaScript code then it passes

# Answer
# Total snippet length 8; test program 83 (C)

Distinguish JavaScript and C from C++, Java, and C#

```
a;

```

Distinguish JavaScript from C

```
0

```

Distinguish C++ from C# and Java

```
#

```

Distinguish C# and Java

```
[:a]

```

C code to determine the language

```
#define C(x)compile(#x)?
main(){puts(C(a;)C(#)C([:a])"J":"C#":"C+":C(0)"C":"JS");}

```

Snippets tested with

C: gcc 4.7.2 with -std=c99
C++: g++ 4.7.2 with -std=c++11
Java: javac 1.7.0\_09
JavaScript: JavaScript-C 1.8.5
C#: Mono C# compiler version 2.10.8.0
> 7 votes

---
Tags: code-golf
---


title: Merge working time periods

text:
# Question
Title: Merge working time periods
You have an array of working time period pairs (from, till) received from user input and written according 24-hour clock format convention. You have to merge these periods if the intersect each other.

For example, if you have (10, 12), (11, 13), (12, 14) you should merge them into (10,14). Also (23, 0) and (0, 1) should be merged into (23, 1).

UPDATE:

@dmckee Let assume that the set of pairs like (10:00, 12:00) is the valid input.

@dude We don't consider Sundays and holidays so all merges should be performed for the common twenty-four hours range.

@steven-rumbalski The result of (0,8), (8,16), (16,0) may be any (x,x) pair, for example, (00:00,00:00).

**Example 1**

Input

```
(09:00,12:00),(11:00,13:00),(17:00,19:00)

```

Output

```
(09:00,13:00),(17:00,19:00)

```

---

**Example 2**

Input

```
(00:00,08:00),(08:00,16:00),(16:00,00:00)

```

Output

```
(00:00)

```

# Answer
> 1 votes
# Python (198 chars)

```
r=[]
p=r.append
l=r+sorted(a<b and (a,b)or p((0,b))or(a,24)for a,b in input())
r[:]=[]
a,b=l[0]
for c,d in l[1:]:
 if c>b:p((a,b));a,b=c,d
 elif b<d:b=d
if b>23:b=a and r.pop(0)[1]
p((a,b))
print r

```

Example:

```
> python merge.py
(10, 12), (11, 13), (12, 14)
[(10, 14)]
> python merge.py
(23,0),(0,1)
[(23, 1)]
> python merge.py
(0,8), (8,16), (16,0)
[(0, 0)]

```

---
Tags: code-golf, date, array
---


title: Non-transitive dice game

text:
# Question
Title: Non-transitive dice game
Those of you who like Numberphile would be familiar with Dr. James Grime, who described a non-transitive dice game on his channel.

The game consists of three 6-faced dice:

* Die 1: 3,3,3,3,3,6
* Die 2: 2,2,2,5,5,5
* Die 3: 1,4,4,4,4,4

Two players each select a die to use. They roll them and the higher die wins, best-of-whatever.

Probabilistically, die 1 beats dies 2 with \>50% chance. Similarly, die 2 beats die 3, and, interestingly, die 3 beats die 1.

Write a program taking `1`, `2` or `3` as input. This indicates the die the user chooses. The program then choose the die that would beat the user and output the results of 21 rolls, and "`Computer/User wins with x points`"

# Rules

* Code-golf, votes as tiebreaker
* You must use RNG (or the likes) to actually simulate the dice rolls.
* I am not too strict on output format. It's okay as long as you show the dices, somehow separate between the 21 rolls (in a way different from how you separate the dice in the same roll), and output that sentence above.
* Input can be stdin, command line argument, from screen, etc.

# Example

**Input**

```
1

```

**Output**

```
4 3
4 3
4 3
4 3
4 3
4 3
4 3
4 3
4 3
4 6
1 3
4 3
4 3
1 3
4 3
1 3
4 3
4 3
4 3
4 3
4 6
 Computer wins with 16 points

```

Here, the user chooses die 1 and his rolls are shown on the right column. The program chooses die 3 and beats him.

# Answer
> 1 votes
### GolfScript, 112 105 characters

```
3,21*{..+6rand<3*+)}%3/\{)\.+-1%>2<.p~<}+,,"User
Computer"n/1$11<=" wins with "+\[.~22+]$1>~+" points"+

```

Run it online.

The script expects the input on STDIN and then prints the outcome of the dice rolls (first column computer, second user) and the final statistics to STDOUT.

# Answer
> 4 votes
## APL (~~106~~ 114)

```
'Computer' 'User'[1+X],'wins with','points',⍨|Z-21×X←11>Z←+/>/⎕←⍉↑{⍵[{?6}¨⍳21]}¨(↓5 6⍴545170074510753⊤⍨18⍴7)[⎕+⍳2]

```

Explanation:

* `(↓5 6⍴545170074510753⊤⍨18⍴7)[⎕+⍳2]`: The big number is a base-7 representation of the dice. We make a 6x5 matrix containing the values of the dice in the order: 2 3 1 2 3. Ask for user input and add this to the vector `1 2`, and select these lines from the matrix. Because the list of dice is shifted, the user now gets the one he selected (on the right) and the computer gets the stronger one.
* `{⍵[{?6}¨⍳21]}¨`: do 21 rolls for each of these two dice.
* `⎕←⍉↑`: put the rolls in matrix form and output them.
* `Z←+/>/`: get the score of the computer (amount of times the computer's value was higher than the user's)
* `X←11>Z`: set `X` to whether the user won (if 11 is higher than the computer's score).
* `'Computer' 'User'[1+X]`. `X` is whether the user won.
* `'wins with','points',⍨|Z-21×X`: `Z` is the computer's score, so if the computer won display `Z`, otherwise display `21-Z`.

# Answer
> 2 votes
# R - 228

```
d=matrix(rep(c(rep(3,5),6,2,2,2,5,5,5,1,rep(4,5)),2),6)
x=scan()
r=expand.grid(Computer=d[,x+2],User=d[,x])[sample(36,21,T),]
print(r)
s=summary.factor(names(r)[max.col(r)])
cat(names(which.max(s)),"wins with",max(s),"points\n")

```

Example run:

```
> source('ntd.R')
1: 2
2:
Read 1 item
     Computer User
28          3    5
31          3    5
36          6    5
18          6    2
11          3    2
31.1        3    5
14          3    2
8           3    2
9           3    2
17          3    2
2           3    2
29          3    5
3           3    2
16          3    2
4           3    2
21          3    5
14.1        3    2
23          3    5
16.1        3    2
17.1        3    2
19          3    5
Computer wins with 14 points

```

# Answer
> 2 votes
## Mathematica ~~208~~ ~~172~~ ~~166~~ 159

Spaces added for clarity

```
b=Boole;{#, Row@{
         If[# > 10, "Play", "Comput"], "er wins with ",
         Max[#, 21 - #], " points"} &@ Total[b[#1 > #2] & @@@ #]} &@
   Table[1 + i + 3 b[6 Random[] > 2 i + 1],{21}, {i, {#, Mod[# + 1, 3]}}] &

```

# Answer
> 1 votes
## Mathematica 234 247

**Code**

```
g@n_ := {t = RandomChoice[{{5, 25, 1, 5}/36 -> {{3, 1}, {3, 4}, {6, 1}, {6, 4}},
         {5, 1, 5, 1}/12 -> {{2, 3}, {2, 6}, {5, 3}, {5, 6}},
         {1, 1, 5, 5}/12 -> {{1, 2}, {1, 5}, {4, 2}, {4, 5}}}[[n]], 21],
         Row[{If[(c = Count[t, {x_, y_} /; y > x]) > 10, "Computer ", "Player "],
         "wins with ", If[c > 10, c, 21 - c], " points"}]}

```

---

**Usage**

> {Player's roll, Computer's roll}

```
g[1]
g[2]
g[3]

```

---

**Explanation**

`n` is the number 1, 2, or 3 that corresponds to the die of the player. Because n also determines (but does not equal) the die of the computer, we can generate all possible rolls of the dice when n=1, n=2, n=3. We can also determine their respective probabilities.

Examine the data right after `RandomChoice`:

> {5, 25, 1, 5}/36 -\> {{3, 1}, {3, 4}, {6, 1}, {6, 4}}

If the player draws die 1, the only possible outcomes are the following 4 pairs

`{{3, 1}, {3, 4}, {6, 1}, {6, 4}}`

The respective probabilities of these pairs are

`{5, 25, 1, 5}/36`, that is,

`{5/36, 25/36, 1/36, 5/36}`

`RandomChoice[<data>, 21]` outputs 21 rolls of the two dice.

# Answer
> 1 votes
## C,  ~~205~~  191

```
p;r(c){return 1+c+3*(rand()%6>2*c);}main(i,c,q,s){for(c=51-getchar();++i<23;printf("%u %u\n",q,s))q=r(c),p+=(s=r(-~c%3))<q;printf("%ser wins with %u points",p<11?"Comput":"Us",p<11?21-p:p);}

```

Reads the user's choice from stdin.

# Answer
> 1 votes
## **Ruby 1.8, 165**

```
i,s,*d=getc,21,[4]*5<<1,[3]*5<<6,[2,5]*3
puts"#{s.times{p r=[i,i-1].map{|o|d[o%3][rand 6]};s+=r[0]<=>r[1]}>s?"Human":"Computer"} wins with #{[s/=2,21-s].max} points"

```

`getc` gets the ascii value of the input (ruby 1.8 only), which happily is congruent modulo 3 to its integer value.

`s` starts out at 21, so `s.times{code}` will execute `code` 21 times and return 21. On each iteration, the loop either adds or subtracts 1 from s depending on who wins, so we can see who won by seeing whether `s` has ended up below 21. Neat so far, but then I need the clumsy expression `[s/=2,21-s].max` to extract the actual number of points. I've long wanted to do arithmetic with the return value of `<=>`, so I'm happy anyway.

# Answer
> 1 votes
# Factor

## With includes: 388

## Without: 300

```
USING: arrays formatting io kernel math math.parser prettyprint random sequences ;
IN: N
CONSTANT: d { { 3 3 3 3 3 6 } { 2 2 2 5 5 5 } { 1 4 4 4 4 4 } }
: p ( -- ) 1 read string>number [ 3 mod 1 + ] keep [ 1 - d nth ] bi@ 2array 21 iota [ drop first2 [ random ] bi@ [ 2array . ] 2keep < ] with map [ ] count [ 11 > "Comput" "Play" ? ] [ "er wins with %d points" sprintf ] bi append print ;

```

Yeah, Factor's not really the language to use when golfing, but it's nice.

# Answer
> 0 votes
# Python 182

```
from random import*
u=2+input()
r=[eval("int(choice(`0x1d67e987c0e17c9`[i%3::3])),"*21)for i in(u,u-1)]
U,C=map(sum,r)
print r,['Us','Comput'][U<C]+'er wins with %d points'%abs(U-C)

```

# Answer
> 0 votes
## R 206

```
u=scan()
D=list(c(rep(3,5),6),c(2,5),c(1,rep(4,5)))
S=sample
U=S(D[[u]],21,T)
C=S(D[[(u+1)%%3+1]],21,T)
print(cbind(U,C))
W=sum(U>C)
I=(W>10)+1
cat(c("Computer","User")[I],"wins with",c(21-W,W)[I],"points")

```

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