# Question
Title: Make StackOverflow Explode (bookmarklet)
Sometimes people get frustrated on the StackExchange network (specifically SO).

Your task is to create a bookmarklet that causes StackOverflow to explode/implode/destroy in some fashion. This will provide a nicer way of dispersing our frustrations.

The Rules:

* it must be in the form of a bookmarklet
* must work in Chrome and Firefox (latest stable)
* jQuery is on the site, so you can use it
* no creating a script tag that pulls explosionThisPage.js or similar

Scoring is the number of characters that need to be copied and pasted, except:

* -1 if you include an explanation
* -5 for each upvote
* -10 if you don't use jQuery
* -10 if it makes an explosion sound
* +9e72 if it actually does harm to the site (F5 should repair the damage)

If the gif's distracting, remove it.

# Answer
> 27 votes
Chicken!

### Score: 46 - 1 (explanation) - 5\*17 (votes) = -40

```
javascript:$('*:not(:has(*))').text('chicken')

```

It simply takes every element with no children and replaces it with the text `'chicken'`.

Sample screenshots:
more chicken
this question chickenified

# Answer
> 29 votes
Here's my entry, which I'll call **the drunkenator**:

```
javascript:void(setInterval(function(){c='1234567890poiuytrewqasdfghjklmnbvcxzZXCVBNMLKJHGFDSAQWERTYUIOP=)(/&%25$%23"!1';$(':not(iframe,script,style)').contents().each(function(){if(this.nodeType==3&&/\S/.test(this.nodeValue)){a=this.nodeValue.split('');x=0;for(i=0;i<a.length;i++){r=Math.random()*9999;if(r<10){x=1;j=c.indexOf(a[i]);a[i]=(r<4%3F(t=a[i-1],a[i-1]=a[i],t):r<5%3F'':r<6%3Fa[i]+a[i]:j<0%3Fa[i]:c.charAt(j+(r<8%3F1:-1)))}}if(x)this.nodeValue=a.join('')}})},100))

```

At 474 chars, it's probably not going to win any golf prizes, but I'm hoping to make up for it in upvotes. :)

Here's the same code de-obfuscated:

```
setInterval(function () {
  var c = '1234567890poiuytrewqasdfghjklmnbvcxzZXCVBNMLKJHGFDSAQWERTYUIOP=)(/&%$#"!1';
  $(':not(iframe,script,style)').contents().each(function () {
    if (this.nodeType==3 && /\S/.test(this.nodeValue)) {
      var a = this.nodeValue.split('');
      var x = 0;
      for (i = 0; i < a.length; i++) {
        r = Math.random() * 9999;
        if (r < 10) {
          x = 1;
          j = c.indexOf(a[i]);
          a[i] = ( r < 4 ? (t = a[i-1], a[i-1] = a[i], t)
                 : r < 5 ? ''
                 : r < 6 ? a[i] + a[i]
                 : j < 0 ? a[i] : c.charAt(j + (r < 8 ? 1 : -1)) );
        }
      }
      if (x) this.nodeValue = a.join('');
    }
  });
}, 100);

```

What it does is randomly mutate the text on the page, swapping adjacent characters, deleting or duplicating characters or replacing them with ones adjacent to them on the keyboard. The effect is kind of subtle at first, but leave it running for a while, and the page content will inevitably decay into a mess of drunken typing:

Ps. The code isn't in any way SO-specific, so it'll work on any website that uses jQuery. Try it on Wikipedia for hilarious results. The idea is based on something I wrote years ago as a creative interpretation of the "99 bottles of beer" challenge: my version introduced a slowly increasing number of typos into each verse, until the last ones were all but unrecognizable. If anyone wants to see it, here's the original Perl code.

# Answer
> 16 votes
I don't know why this was downvoted, I like it :)

This isn't the shortest, but I think it's pretty:

**133 chars** -1

```
javascript:(function(){setInterval(function(){$("div, span").eq(Math.round(Math.random()*$("div, span").length)).hide(500)},90)}());

```

Ungolfed:

```
javascript:(function(){
         window.setInterval(function() {
                 i = Math.round(Math.random() * $("div, span").length);
                 $("div, span").eq(i).hide("slow");
         } , 90);
}());

```

Explanation: I hope this counts, this script implodes the site instead of exploding it ;) This just picks a random div or span every 90ms and closes it slowly..

# Answer
> 11 votes
Because it was not defined if the higher or lower score wins...

```
javascript:$(".vote-down-off").click()

```

Base: 38
Bonis:

* +9e72 Permanent damage.

### Final score: 9000000000000000000000000000000000000000000000000000000000000000000000038

Btw, I did not try it.

# Answer
> 8 votes
## My pupose 245 chars.

Mostly not the shorter, but I like it ;-)

```
javascript:document.body.innerHTML+='<img%20id="bigMsk"%20src="https://i.stack.imgur.com/VWPZg.gif">';document.getElementById('bigMsk').setAttribute('style','z-index:1;opacity:.6;display:block;position:fixed;top:0;left:0;width:100%;height:100%;');

```

-1: Explanation:

* I use the nice offered animated gif image from question,
* With the help of CSS, I put them over the page in full page, with a 60% opacity.

:

```
document.body.innerHTML+=
   '<img%20id="bigMsk"%20src="https://i.stack.imgur.com/VWPZg.gif">';
document.getElementById('bigMsk').setAttribute('style',
    'z-index:1;
     opacity:.6;
     display:block;
     position:fixed;
     top:0;
     left:0;
     width:100%;
     height:100%;
');

```

Mostly readable by itself ;-)

-10 No JQuery

### Alternative:

There is an alternative:

```
javascript:document.body.innerHTML+='<img%20id="bigMsk"%20src="https://i.stack.imgur.com/aTtWM.gif">';document.getElementById('bigMsk').setAttribute('style','z-index:1;opacity:.6;display:block;position:fixed;top:0;left:0;width:100%;height:100%;');

```

Based on unmodified GIF, found at Wikimedia Commons: File:Animated fire by nevit.gif

**Image:**

### Sample:

# Answer
> 5 votes
Ok, I think this should meed the criteria:

```
javascript:document.write("<h1>Exploded</h1>")

```

Replaces the current page with "Exploded"

Score: 46
-1 Explaination
-10 No jQuery

## 35

# Answer
> 5 votes
This one's enjoyable, and causes quite a bit of lag too :D

```
javascript:setInterval(function(){document.body.innerHTML=document.body.innerHTML.replace(/\d+/g,function(){return Math.random()*100|0});},500)

```

It just sets an interval that replaces all strings of digits with a random number from 0 to 100. Twice per second. It creates a bunch of errors, as you might expect, and I could fix it to stop all the 404s when image URLs are changed, but I think it's more fun this way and it's code golf. :D

Score:

* 132 base
* -1 explanation
* -5 upvote
* -10 no jQuery

Total score: 116

# Answer
> 4 votes
# 165 chars (164 points)

-1 for explaination

Here's my attempt. It's not particularly short, but it's fun.

```
javascript:r=Math.random;$("a,span,p").each(function(){var a=$(this);a.css({position:"relative"});a.delay(1E4*r()).animate({left:9E3*r()-4E3,top:9E3*r()-4E3},555)});

```

It slides individual elements off the page in random directions. I specifically included span because of the syntax highlighting (each color has a separate span).

```
r = Math.random;
$('a,span,p').each(function () {
    var t = $(this);
    t.css({
        position: 'relative'
    });

    t.delay(r()*10000).animate({
        left: r() * 9e3 - 4e3,
        top: r() * 9e3 - 4e3
    }, 555);
});

```

It of course could be shortened by removing some of the tags, but let me know if there are any ways to shorten it without reducing the performance.

# Answer
> 4 votes
# *181* 151 chars - 1 (explanation) - 10 (no jQuery) = 140 points

```
javascript:i=setInterval(function(){for(var a=document;0!==a.childNodes.length;)a=a.childNodes[a.childNodes.length-1];a!==document?a.parentNode.removeChild(a):clearInterval(i)},50);

```

A few more characters can be saved by omiting the `function(){` and using a string instead. Also note the extraction of commonly used properties, e.g., `c='childNodes` allows us to do `z[c]` instead of `z.childNodes`.

```
javascript:h=setInterval('d=z=document;c="childNodes";for(l="length";z[c][l];z=z[c][z[c][l]-1]);z!=d?z.parentNode.removeChild(z):clearInterval(h)',50);

```

I guess I could make less points by using jQuery and not traversing properties, but oh well.

**Ungolfed:**

```
var intervalHandle = setInterval(function() {
    var lastElement = document;
    //get last element
    while (lastElement.childNodes.length !== 0) {
        lastElement = lastElement.childNodes[lastElement.childNodes.length - 1];
    }

    if(lastElement !== document) {
        lastElement.parentNode.removeChild(lastElement);
    } else {
        clearInterval(intervalHandle);
    }
}, 50);

```

Basically this finds the latest DOM element on the page and removes it. Then keeps doing that for every 50 milliseconds, which I found to be a kind-of-average nice speed to see a page getting ripped from the ground up. It's therapeutic, I swear it.

Disclaimer: I had made this some time ago and decided to share it, since it seems appropriate here. The source is at my GitHub repository.

# Answer
> 3 votes
### Javascript, 281

```
javascript:$('body').html().split('<code>javascript:').forEach(function (a) {if (a.indexOf("location")*a.indexOf("write")*a.indexOf("noscript")==-1) try{exec(a.split("</code>")[0].replace(/&#(\d+)/g, function(match, dec) {return String.fromCharCode(dec);}))} catch (e) {}});void 0;

```

It gets every response to the question in the form of `<code>javascript:(stuff)</code>` that doesn't change the location, and runs all of them.

# Answer
> 2 votes
I like this effect. It basically toggles a slide effect for every div on the site every 1 millisecond.

```
javascript:setInterval(function(){$('div').toggle()},1)

```

**Score**

```
56
-1 Explanation
--------------
55 Total

```

---
Tags: code-challenge, javascript
---


# Question
Title: Check whether there are more even than odd numbers on any given nested list
Take any type of nested list(s) containing numbers. Check for how many even/odd numbers are within and output even, same or odd (-1, 0, 1) in some way.

Example:

```
[[1,2,3],4,[5,6],[[7,8], 9]] => 5 odd > 4 even => odd or -1
[1,2,2,1,2,2,2]              => 5 even > 2 odd => even or 1
[1,2,2,1]                    => 2 even = 2 odd => same or 0

```

# Answer
> 3 votes
## Python - 63

This returns a negative number if its got more evens, `0` if their are an equal amount or a positive number if there are more odds.

```
x=input()
i=0
for o in x:
 try:x+=o
 except:i+=o%2-.5
print i

```

edit: Type checking, who needs that, lets just stab blindly.

# Answer
> 1 votes
## R 58

This was written at a time the OP was asking for two "even" or "odd" possible outputs.

```
function(x)c("even","odd")[which.max(table(unlist(x)%%2))]

```

Example usage:

```
(function(x)c("even","odd")[which.max(table(unlist(x)%%2))])(
   list(list(1, 2, 3), 4, list(5, 6), list(list(7, 8), 9)))
# [1] "odd"

```

# Answer
> 1 votes
# Befunge 98 - 19

```
&2%6*j\1+\2j1+3j@.`

```

Outputs 1 if even, 0 if odd or the same. I'm still trying to figure out how to indicate that they are the same. However, I have not tested this because I don't have a Befunge 98 compiler. It works as follows:

```
&   receives input as a number, all parts that aren't numbers are ignored and skipped
2%  takes that number and divides it by two, then gets the remainder (1 if odd, 0 if even)
6*j jump 6 characters if odd, 0 if even

when even:
\   swap top two numbers on stack (I'm storing evens under the odds)
1+  add one to that value
\   swap back
2j  jump 2 characters

when odd:
1+  add 1 to top number on stack

3j  jump 3 characters (to end of line ie the beginning (Befunge wraps))

```

When `&` is hit again, if there are no more values, it acts like a reflector, sending the instruction pointer back the other way and running this:

```
@.`

```

(executed in reverse order):

```
` compares the even and odd values, if even is greater, then push 1, else 0
. prints it out
@ ends the program

```

---

With one simple change, it can be made to print some negative number if there are more odds, some positive number if there are more evens, and 0 if there are the same amount:

```
&2%6*j\1+\2j1+3j@.-

```

# Answer
> 1 votes
# R, 64

### three possible outputs

```
function(x)c("even","same","odd")[sign(mean(unlist(x)%%2)-.5)+2]

```

Examples:

```
(function(x)c("even","same","odd")[sign(mean(unlist(x)%%2)-.5)+2])(
   list(list(1, 2, 3), 4, list(5, 6), list(list(7, 8), 9)))
[1] "odd"

(function(x)c("even","same","odd")[sign(mean(unlist(x)%%2)-.5)+2])(
   list(list(2, 3), 4))
[1] "even"

(function(x)c("even","same","odd")[sign(mean(unlist(x)%%2)-.5)+2])(
  list(list(2, 3), list(4, 5)))
[1] "same"

```

# Answer
> 1 votes
# k

34 characters.

Outputs `o` for odd, `e` for even, `s` for same.

```
{"ose"1+{(x>0)-x<0}@+/-1 xexp,//x}

```
~~```
{(`s#-0w -.5 .5!"ose")@+/-1 xexp,//x}

```~~

Example:

```
{"ose"1+{(x>0)-x<0}@+/-1 xexp,//x}((1 3;5 10);12 2 4 6 8)
"e"

```

# Answer
> 0 votes
## Golf-Basic 84, 17

```
i`Ad`fpart(A/2)*2

```

Returns `0`s for even numbers and `1`s for odd numbers. Accepts nested arrays - 1D, 2D, 3D, 4D, etc.

---

**Old version, 30 characters:**

```
i`A@fpart(A/2)*2t`ODD"#t`EVEN"

```

**Explanation** (for old version)

```
i`A

```

Store input in A. Accepts arrays, e.g. `{1,2,3,4}` or `{{1,2},3,{4,5,{6,7}},8}`

```
@fpart(A/2)*2t`ODD"#t`EVEN"

```

If (`@`) one or more numbers in array `A` are odd, display `ODD`. Else (`#`) display `EVEN`.

# Answer
> 0 votes
## JavaScript, 65

```
c=l=>l.reduce((a,b)=>a+(+b?b%2-.5:c(b)),0),l=>c(l)<0?"even":"odd"

```

Defaults to “odd” if there are equal numbers of each. Requires arrow function support, which currently means “SpiderMonkey”.

If you don’t mind output as a number, it’s just this part, at **42**:

```
c=l=>l.reduce((a,b)=>a+(+b?b%2-.5:c(b)),0)

```

# Answer
> 0 votes
## Ti-Basic 84, 26 characters

```
:Input A:Disp fpart(A/2)*2

```

Returns `1` for odd numbers and `0` for even numbers. Takes nested arrays - 1D, 2D, 3D, 4D, 5D, etc.

---

Old version, **50** characters:

```
:Input A:If fpart(A/2)*2:Disp"ODD":Else:Disp"EVEN"

```

Takes arrays like `{1,2,3}` and also `{1,{2,3},4,{5,{6,7}},{{8,9},10},11}`

Returns `EVEN` for all even and `ODD` if it contains odd.

# Answer
> 0 votes
## JavaScript, 51+

### Variation 1, 61 or 51

Reads input via `prompt`, outputs via `alert`, encodes answer as a number with sign denoting if more evens or odds.

```
b=0;prompt().replace(/\d+/g,function(s){b+=s%2*2-1});alert(b) // ES5, 61
b=0;prompt().replace(/\d+/g,s=>b+=s%2*2-1);alert(b) // ES6, 51

```

### Variation 2, 72 or 49

As above, but as a function taking an array instead of using `prompt`/`alert`.

```
function f(s){b=0;return s.big?b+=s%2*2-1:s.join().replace(/\d+/g,f)&&b} // ES5, 72
f=a=>b=0,a.join().replace(/\d+/g,s=>b+=s%2*2-1),b // ES6, 49

```

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


title: Simple One Game Blackjack

text:
# Question
Title: Simple One Game Blackjack
This is a very stripped down version of A BlackJack KOTH contest...

This is the goal:

Upon the execution: There are two inputs, "H" to hit (have the code deal a card), "S" to stand (Stop getting cards, and let dealer try to win).

Coding Rules:

1. There is no betting or splitting of hands, for simplicity of the challenge.
2. Suits are HDCS; standing for Hearts, Diamonds, Clubs and Spades respectively.
3. Trumps must be formatted as A23456789TJQK, where T is the 10; therefore TH is the 10 of Hearts, etc.
4. A is worth 1 or 11. Face cards are worth 10 points. A perfect game is 21 points.
5. If you go over 21 points, the output along with the cards must show "BUST".
6. If the dealer goes over 21 points and you're standing, output with cards must show "WIN"
7. If the dealer beats you even though you're standing, output with cards must show "LOSE"
8. If the dealer matches your score on standing, output with cards must show "PUSH"
9. Dealer must stand on 17 through to 21.
10. If you Stand, it calculates your score and displays it (see below), and then goes into dealer play mode. If the dealer stands or busts, it calculates its score and displays it.
11. Standard 52 cards in a deck, no duplicates can be generated.
12. Output must resemble the following:

```
H
Your hand: 3H
H
Your hand: 3H 8S
H
Your hand: 3H 8S 9D
S
Standing... Your hand: 3H 8S 9D = 20 points
My hand: 2C 5H 8H 9S = 24 points
WIN

```
13. Shortest code wins

# Answer
## Golf-Basic 84, 852 characters (ALL rules observed)

```
:"YOUR HAND:"_Str1:-1_X:0_O:0_A:0_P:2_H:3_2l`Ii`I@I=2o`H#o`Sl`H:Str1+" "_Str1:round(rand*13,0)_R@R=0:Str1+"A"_Str1@R=1:Str1+"2"_Str1@R=2:Str1+"3"_Str1@R=3:Str1+"4"_Str1@R4:Str1+"5"_Str1@R=5:Str1+"6"_Str1@R=6:Str1+"7"_Str1@R=7:Str1+"8"_Str1@R=8:Str1+"9"_Str1@R=9:Str1+"10"_Str1@R=10:Str1+"J"_Str1@R=11:Str1+"Q"_Str1@R=12:Str1+"K"_Str1@R=1:A+10_A@R<9:P+R+1_P#P+10_P:round(rand*4,0)_R@R=0:Str1+"H"_Str1@R=1:Str1+"D"_Str1@R=2:Str1+"C"_Str1@R=3:Str1+"S"_Str1d`Str1@P>20:o`So`Il`St`STANDING... "+Str1+", POINTS:"d`P@P=21 or P+A=21:"WIN"_Str2@P>21:"BUST"_Str2:round(rand*8,0)_R:"MY HAND: "_Str3l`X:X+1_X:round(rand*8,0)@R=0:Str3+"9H"_Str3@R=1:Str3+"9D"_Str3@R=2:Str3+"9C"_Str3@R=3:Str3+"9S"_Str3@R4:Str3+"JH"_Str3@R=5:Str3+"QD"_Str3@R=6:Str3+"KC"_Str3@R=7:Str3+"KS"_Str3@R<4:O+9_O#:O+10_O@Xo`E#o`Xl'Et`Str3+"= POINTS:"d`O@P=O:"PUSH"_Str2@P<O:"LOSE"_Str2d`Str2

```

Coded all by myself!

**Explanation**

* Initialize variables; put `0` in `P` and `"YOUR HAND:"` in `Str1`
* Take input, either `H` or `S` (no quotes needed)
* Based on input, goto `Lbl H` or `Lbl S`
* If input is `H`, generate a random card, add a space, a number/letter, and a suit to `Str1`
* Based on the card generated, add the value of the card to `P` and additionally add 1 to `A` (ace count)
* Get more input
* If input is `S`, calculate the points and the dealer's points
* Put `WIN` or `BUST` in `Str2` depending on the points generated
* Display the dealer's hand
* Calculate your points and the dealer's points, conditionally put `LOSE` or `PUSH` in `Str2`
* Display `WIN`, `PUSH`, `LOSE`, or `BUST`

**Sample output**

```
?H
YOUR HAND: 9C
?H
YOUR HAND: 9C 7S
?H
YOUR HAND: 9C 7S 4S
?S
STANDING... YOUR HAND: 3H 8S 9D, POINTS:
                                      20
MY HAND: 9H KS = POINTS:
                                      19
WIN

```
> 0 votes

# Answer
## Javascript 838

The very first version, not optimized ! All rules are not fully observed, :-o

```
!function(){var f=require("readline").createInterface(process.stdin,process.stdout),g=[],h=function(){for(var b;!b||-1<g.indexOf(b);)b="A23456789TJQK".charAt(13*Math.random()|0)+"HDCS".charAt(4*Math.random()|0);g.push(b);return b},k=function(b){var a=0,d=0;for(z=b.length;z--;){var c=b[z].charAt(0);/[TJQK]/.test(c)?a+=10:/[2-9]/.test(c)?a+=+c:"A"==c&&(d++,a++)}for(;d--;)21>=a+10&&(a+=10);return a};(function(){var b=[],a=[],d=0,c=0;f.prompt();f.on("line",function(e){e=e.charAt(0);"H"==e&&(b.push(h()),
c=k(b),console.log("Your hand: "+b+" = "+c+" points"),21<c&&(console.log("LOSE"),process.exit(0)));if("S"==e){for(;17>(d=k(a));)a.push(h());console.log("My hand: "+a+" = "+d+" points");21<d||d<c?console.log("WIN"):d>c?console.log("LOSE"):console.log("DRAW");process.exit(0)}f.prompt()}).on("close",function(){process.exit(0)})})()}();

```

Execute it with nodeJS
> 0 votes

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


title: Compressing a DNA-like string

text:
# Question
Title: Compressing a DNA-like string
### Challenge:

Write a a program to take an array of 24 4-letter strings, and output a compressed (lossless) representation of the array. You should also provide a program to decompress your representations.

### Input:

The input will be comprised of 4 letter words using each of `[G,T,A,C]` exactly once (e.g. `GTAC`, `ATGC`, `CATG`, etc). There are always exactly 24 words, so the full input is something like:

```
GTAC CATG TACG GACT GTAC CATG TACG GACT GTAC CATG TACG GACT GTAC CATG TACG GACT GTAC CATG TACG GACT GTAC CATG TACG GACT

```

So there are \\$4!=24\\$ possibilities for each word, and 24 words in total.

### Output:

The output should be a printable ASCII string that can be decompressed back into the input string. Since this is lossless compression, each output should match to exactly one input.

### Example:

```
>>> compress(["GTAC", "CATG", "TACG", "GACT", "GTAC", "CATG", "TACG", "GACT", "GTAC", "CATG", "TACG", "GACT", "GTAC", "CATG", "TACG", "GACT", "GTAC", "CATG", "TACG", "GACT", "GTAC", "CATG", "TACG", "GACT"])
"3Ax/8TC+drkuB"

```

### Winning Criterion

Your code should minimize the output length. The program with the shortest output wins. If it's not consistent, the longest possible output will be the score.

**Edit**: Based on helpful feedback comments, I would like to amend the criterion to add:

If two entries have the same results, the shortest code measured in characters wins. If an entry is length dependent, a length of 1 million words is the standard.

However, I fear the community angrily telling me I didn't say it right and downvoting me to the abyss, so I leave to community editors to see if it makes sense with code golf traditions

# Answer
## Python (output-length: 18 or 19, mean 18.80)

```
#list of the 24 possible words
Lbase = ['GTAC','GTCA','GATC','GACT','GCTA','GCAT','TGAC',\
'TGCA','TAGC','TACG','TCGA','TCAG','AGTC','AGCT','ATGC',\
'ATCG','ACGT','ACTG','CGTA','CGAT','CTGA','CTAG','CAGT','CATG']

#base-64 alphabet (used only in the output string-representation)
alph = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789+/'

#change a bijective list-representation base from b to newb
def chg_bij_base(L, b, newb):
    n = sum([L[i]*b**i for i in range(len(L))])
    L = []
    while n > 0:
        L.append(1+(n-1)%newb)
        n = (n-1)//newb
    return L

#convert a bijective list-repr. to base-64 string-repr.
def list_to_str(Lin):
    L24 = [Lbase.index(w)+1 for w in Lin]
    L64 = chg_bij_base(L24,24,64)
    return ''.join([alph[i-1] for i in L64])

#convert a base-64 string to the corresponding base-64 list-repr.
def str_to_list(s):
    L64 = [alph.index(c)+1 for c in s]
    L24 = chg_bij_base(L64,64,24)
    return [Lbase[i-1] for i in L24]

```

Test run:

```
Lin = ["GTAC", "CATG", "TACG", "GACT", "GTAC", "CATG", "TACG", "GACT", "GTAC", "CATG", "TACG", "GACT", "GTAC", "CATG", "TACG", "GACT", "GTAC", "CATG", "TACG", "GACT", "GTAC", "CATG", "TACG", "GACT"]

#convert input list to a base-64 string
lts = list_to_str(Lin)

#convert the base-64 str back to the list
stl = str_to_list(lts)

print(len(lts))
print(lts)
print(stl == Lin)

```

Test output:

```
18
acFZIBuiiZJ+dwUn2V
True

```

This uses bijective numeration (which has no 0 digit) to get invertibility.

**NB**: When using base-64 with this method, all output strings for the above problem are either 18 or 19 characters. (A million random inputs gave an average of 18.80.) The same method works with other bases:

```
base         output-length
---------    -------------
56 - 58      19
59 - 69      18 or 19
70 - 73      18
74 - 88      17 or 18
89 - 96      17
...          ...
233 - 256    14

```
> 6 votes

---
Tags: string, code-challenge, compression
---


# Question
Title: Calculate the bitruncated cubic distance between two points
The truncated octahedron is a shape that has the interesting property that it can tessellate an entire 3D space so that any two solids that meet by an edge or corner also meet by a face, in a configuration called the bitruncated cubic honeycomb.

This gives it the special property that there is only one metric for adjacency distance \[unlike a cubic grid where two cubes touching by only a corner have a face distance of 3\], a property which is shared by a hexagonal grid in two dimensions.

Any solid in the bitruncated cubic honeycomb can be represented by the 3D coordinates `(a+h, b+h, c+h)` where `a, b, c` are integers and `h` is either 0 or 1/2. Any solid at `(x, y, z)` is adjacent to the solids at the following locations:

```
x, y, z+1
x, y, z-1
x, y+1, z
x, y-1, z
x+1, y, z
x-1, y, z
x+1/2, y+1/2, z+1/2
x+1/2, y+1/2, z-1/2
x+1/2, y-1/2, z+1/2
x+1/2, y-1/2, z-1/2
x-1/2, y+1/2, z+1/2
x-1/2, y+1/2, z-1/2
x-1/2, y-1/2, z+1/2
x-1/2, y-1/2, z-1/2

```

Your task is to build a program that, given the locations of two truncated octahedrons in the above arrangement, finds their distance. You can take input in any format you wish.

The shortest code to do this in any language wins.

# Answer
# Golfscript, ~~10~~ 13 characters

```
~{$~\-}%$~+\;

```

input: a space-separated array of three two-element arrays of integers, wrapped in square brackets. Each pair of integers denotes the coordinates of both octahedra in one axis. If half-coordinate inputs are to be supported, the input should be scaled up by an even factor (say, 10).

output: a single integer, scaled up by the same amount as the input

reads: "eval the input, for each axis: {sort both coordinates, then subtract the smaller from the larger}, sort the differences, then dump them onto the stack (resulting in three separate numbers), add the top two (= largest two coordinates) and discard the element just below".

proof:

the algorithm to reach a destination in this amount of steps is:

* If all three coordinate differences are nonzero, make a diagonal step. This reduces all three differences by 0.5, meaning their order doesn't change and the sum of the largest two differences reduces by 1
* If only one coordinate difference is nonzero, make an orthogonal step. This reduces the largest difference by 1
* If two of the difference are nonzero, either of these steps can be chosen.

Thus, this algorithm never underestimates the distance. Also, it is not possible to reduce the sum of top largest two differences by more than 1 in a single step, meaning this algorithm never overestimates either. Thus, the algorithm "sum of the largest two absolute values of coordinate differences" is correct.

example:

```
;"[[20 0] [30 0] [20 -20]]"
~{$~\-}%$~+\;
#70

```

test: http://golfscript.apphb.com/?c=OyJbWzIwIDBdIFszMCAwXSBbMjAgLTIwXV0iCn57JH5cLX0lJH4rXDs%3D
> 1 votes

# Answer
## APL, ~~14~~ 13

```
x+.×1<⍋x←|⎕-⎕

```

1 char saving if I'm allowed to change system variables in configurations

Prompts for input twice, enter space-separated coords both times.

Thanks to Jan
> 1 votes

---
Tags: code-golf
---


title: Need change of 78 cents

text:
# Question
Title: Need change of 78 cents
You bought a tasty **Orange** in the supermarket and got **78** cents change. How many possible ways the supermarket guy can give you the change using 1,5,10 or 25 coins

* **Input**: Change amount
* **Output**: The number of possible ways to give the change.

Order is not important 1,5 is same as 5,1

Win conditions:

1. **Best performance**
2. **Shortest code**

*Also please add the result for 78 in your title.*

# Answer
# Mathematica answer= 121, chars=~~74~~ 37

\[121 ways to give change of $0.78, in pennies, nickels, dimes, and quarters.\]

**Method 1**: FroebeniusSolve

This gives all the ways to solve the Frobenius equation `p + 5n + 10d + 25q = c`:

```
FrobeniusSolve[{1, 5, 10, 25}, #]&

```

The number of ways is (37 chars):

```
Length@FrobeniusSolve[{1,5,10,25},#]&

```

**Examples**

Solutions are of the form, `{pennies, nickels, dimes, quarters}`:

```
 FrobeniusSolve[{1, 5, 10, 25}, #]&[21]

```

> {{1,0,2,0}, {1,2,1,0}, {1,4,0,0}, {6,1,1,0}, {6,3,0,0}, {11,0,1,0}, {11,2,0,0}, {16,1,0, 0}, {21,0,0,0}}

---

```
Length@FrobeniusSolve[{1,5,10,25},#]&[78]

```

> 121

---

**How many ways are there to give change to (.01 to $2.50)?**

```
    Length@FrobeniusSolve[{1,5,10,25},#]&/@Range[250] // AbsoluteTiming

```

Timing: 2.004 sec

> {2.00398, {{1, 1}, {2, 1}, {3, 1}, {4, 1}, {5, 2}, {6, 2}, {7, 2}, {8, 2}, {9, 2}, {10, 4}, {11, 4}, {12, 4}, {13, 4}, {14, 4}, {15, 6}, {16, 6}, {17, 6}, {18, 6}, {19, 6}, {20, 9}, {21, 9}, {22, 9}, {23, 9}, {24, 9}, {25, 13}, {26, 13}, {27, 13}, {28, 13}, {29, 13}, {30, 18}, {31, 18}, {32, 18}, {33, 18}, {34, 18}, {35, 24}, {36, 24}, {37, 24}, {38, 24}, {39, 24}, {40, 31}, {41, 31}, {42, 31}, {43, 31}, {44, 31}, {45, 39}, {46, 39}, {47, 39}, {48, 39}, {49, 39}, {50, 49}, {51, 49}, {52, 49}, {53, 49}, {54, 49}, {55, 60}, {56, 60}, {57, 60}, {58, 60}, {59, 60}, {60, 73}, {61, 73}, {62, 73}, {63, 73}, {64, 73}, {65, 87}, {66, 87}, {67, 87}, {68, 87}, {69, 87}, {70, 103}, {71, 103}, {72, 103}, {73, 103}, {74, 103}, {75, 121}, {76, 121}, {77, 121}, {78, 121}, {79, 121}, {80, 141}, {81, 141}, {82, 141}, {83, 141}, {84, 141}, {85, 163}, {86, 163}, {87, 163}, {88, 163}, {89, 163}, {90, 187}, {91, 187}, {92, 187}, {93, 187}, {94, 187}, {95, 213}, {96, 213}, {97, 213}, {98, 213}, {99, 213}, {100, 242}, {101, 242}, {102, 242}, {103, 242}, {104, 242}, {105, 273}, {106, 273}, {107, 273}, {108, 273}, {109, 273}, {110, 307}, {111, 307}, {112, 307}, {113, 307}, {114, 307}, {115, 343}, {116, 343}, {117, 343}, {118, 343}, {119, 343}, {120, 382}, {121, 382}, {122, 382}, {123, 382}, {124, 382}, {125, 424}, {126, 424}, {127, 424}, {128, 424}, {129, 424}, {130, 469}, {131, 469}, {132, 469}, {133, 469}, {134, 469}, {135, 517}, {136, 517}, {137, 517}, {138, 517}, {139, 517}, {140, 568}, {141, 568}, {142, 568}, {143, 568}, {144, 568}, {145, 622}, {146, 622}, {147, 622}, {148, 622}, {149, 622}, {150, 680}, {151, 680}, {152, 680}, {153, 680}, {154, 680}, {155, 741}, {156, 741}, {157, 741}, {158, 741}, {159, 741}, {160, 806}, {161, 806}, {162, 806}, {163, 806}, {164, 806}, {165, 874}, {166, 874}, {167, 874}, {168, 874}, {169, 874}, {170, 946}, {171, 946}, {172, 946}, {173, 946}, {174, 946}, {175, 1022}, {176, 1022}, {177, 1022}, {178, 1022}, {179, 1022}, {180, 1102}, {181, 1102}, {182, 1102}, {183, 1102}, {184, 1102}, {185, 1186}, {186, 1186}, {187, 1186}, {188, 1186}, {189, 1186}, {190, 1274}, {191, 1274}, {192, 1274}, {193, 1274}, {194, 1274}, {195, 1366}, {196, 1366}, {197, 1366}, {198, 1366}, {199, 1366}, {200, 1463}, {201, 1463}, {202, 1463}, {203, 1463}, {204, 1463}, {205, 1564}, {206, 1564}, {207, 1564}, {208, 1564}, {209, 1564}, {210, 1670}, {211, 1670}, {212, 1670}, {213, 1670}, {214, 1670}, {215, 1780}, {216, 1780}, {217, 1780}, {218, 1780}, {219, 1780}, {220, 1895}, {221, 1895}, {222, 1895}, {223, 1895}, {224, 1895}, {225, 2015}, {226, 2015}, {227, 2015}, {228, 2015}, {229, 2015}, {230, 2140}, {231, 2140}, {232, 2140}, {233, 2140}, {234, 2140}, {235, 2270}, {236, 2270}, {237, 2270}, {238, 2270}, {239, 2270}, {240, 2405}, {241, 2405}, {242, 2405}, {243, 2405}, {244, 2405}, {245, 2545}, {246, 2545}, {247, 2545}, {248, 2545}, {249, 2545}, {250, 2691}}}

---

**Method 2**: Solution by `Solve` (66 chars).

This solves the same equation listed in Method 1, albeit by a more standard method, `Solve`:

```
f[c_]:=Solve[p +5n+10d+25q==c &&p>=0&&n>= 0&&d>=0&&q>= 0,{p,n,d,q},Integers]

```

The number of ways is (74 chars):

```
g@c_:= Length@Solve[p +5n+10d+25q==c &&p>=0&&n>= 0&&d>=0&&q>= 0,{p,n,d,q},Integers]

```

**Examples**

```
 f[21]

```

> {{p → 1, n → 0, d → 2, q → 0}, {p → 1, n → 2, d → 1, q → 0}, {p → 1, n → 4, d → 0, q → 0}, {p → 6, n → 1, d → 1, q → 0}, {p → 6, n → 3, d → 0, q → 0}, {p → 11, n → 0, d → 1, q → 0}, {p → 11, n → 2, d → 0, q → 0}, {p → 16, n → 1, d → 0, q → 0}, {p → 21, n → 0, d → 0, q → 0}}

---

```
 Length[f[78]]

```

> 121

---

**How many ways are there to give change to (.01 to $2.50)?**

```
{#, g[#]} & /@ Range[250] // AbsoluteTiming

```

Timing: 4.72 sec
> 4 votes

# Answer
# K3 (kona), 121.

Simple dynamic progamming. 57 chars.

```
cg:{*{+/x{(y _ x),y#0}/:y*!1+(#x)%y}/[(x#0),1;1 5 10 25]}

  cg 78
121

```

Calculate all results up to 250 cents

```
  {{+/x{(y _ x),y#0}/:y*!1+(#x)%y}/[(x#0),1;1 5 10 25]} 250
2691 2545 2545 2545 2545 2545 2405 2405 2405 2405 2405 2270 2270 2270 2270 2270 2140 2140 2140 2140 2140 2015 2015 2015 2015 2015 1895 1895 1895 1895 1895 1780 1780 1780 1780 1780 1670 1670 1670 1670 1670 1564 1564 1564 1564 1564 1463 1463 1463 1463 1463 1366 1366 1366 1366 1366 1274 1274 1274 1274 1274 1186 1186 1186 1186 1186 1102 1102 1102 1102 1102 1022 1022 1022 1022 1022 946 946 946 946 946 874 874 874 874 874 806 806 806 806 806 741 741 741 741 741 680 680 680 680 680 622 622 622 622 622 568 568 568 568 568 517 517 517 517 517 469 469 469 469 469 424 424 424 424 424 382 382 382 382 382 343 343 343 343 343 307 307 307 307 307 273 273 273 273 273 242 242 242 242 242 213 213 213 213 213 187 187 187 187 187 163 163 163 163 163 141 141 141 141 141 121 121 121 121 121 103 103 103 103 103 87 87 87 87 87 73 73 73 73 73 60 60 60 60 60 49 49 49 49 49 39 39 39 39 39 31 31 31 31 31 24 24 24 24 24 18 18 18 18 18 13 13 13 13 13 9 9 9 9 9 6 6 6 6 6 4 4 4 4 4 2 2 2 2 2 1 1 1 1 1

```

Time to do so (in milliseconds)

```
 \t {{+/x{(y _ x),y#0}/:y*!1+(#x)%y}/[(x#0),1;1 5 10 25]} 250
10

```

Time to calculate up to 5000 cents: \t {{+/x{(y _ x),y#0}/:y\*!1+(#x)%y}/\[(x#0),1;1 5 10 25\]} 5000 360
> 3 votes

# Answer
result=121, javascript with memoize (160 chars)

```
c=[25,10,5,1]
d=[[1],[1],[1],[1]]
function f(x,y){
    return d[x][y]||(d[x][y]=c.slice(x).reduce(function(i,j,k){
        return i+(j>y?0:f(x+k,y-j))
    },0))
}
alert(f(0,prompt()))

```

result=121, javascript without memoize (126 chars)

```
c=[25,10,5,1]
function f(x,y){
    return y?c.slice(x).reduce(function(i,j,k){
        return i+(j>y?0:f(x+k,y-j))
    },0):1
}
alert(f(0,prompt()))

```
> 2 votes

# Answer
# J, 50 48 40

### result: 121

```
g=.{[:+//.@(*/)/0=1 5 10 25|"0 _ ]@i.@>:

```

Using generating functions approach. I'd say performance is not bad and can be easily made much better.

```
g 78
121
g 248
2545

```

Timing:

```
time'g 78'
0.000254s

```
> 1 votes

# Answer
## Haskell - 51 / 69

Answer: 121

```
_%0=1;[]%_=0;(x:y)%m=sum[y%(m-i*x)|i<-[0..m`div`x]]

```

Call notation: `[1,5,10,25]%78`

Or more complete with an extra line:

```
f=([1,5,10,25]%)

```

The call is just: `f 78`

Efficiency test (should be comparable with David Carraher):

```
main=mapM_(print.([1,5,10,25]%))[1..250]

> ghc -O2 frob.hs && time ./frob
 - -
./frob  1.81s user 0.02s system 99% cpu 1.843 total

```
> 0 votes

---
Tags: code-challenge
---


# Question
Title: Generate a sequence with unique subsequences
The string `2123132133` has the property that no subsequence of length 3 is the same as any other subsequence of length 3.

Your task is to build a program that will output as long of a string as possible that satisfies this property for sequences of length 9 with the characters from `1` to `9`.

The source code of your program may not be longer than 16 kilobytes (16,384 bytes). The program that wins is the one that outputs the longest sequence of digits from `1` to `9` such that no subsequence of 9 digits is the same.

# Answer
> 2 votes
What I'm starting with here is a De Bruijn sequence. Stealing some reference code on the topic, here is my submission:

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

def de_bruijn(k, n):
    """ De Bruijn sequence for alphabet size k and subsequences of length n. """
    a = [0] * k * n
    sequence = []
    def db(t, p):
        if t > n:
            if n % p == 0:
                for j in range(1, p + 1):
                    sequence.append(a[j])
        else:
            a[t] = a[t - p]
            db(t + 1, p)
            for j in range(a[t - p] + 1, k):
                a[t] = j
                db(t + 1, t)
    db(1, 1)
    return sequence

seq = de_bruijn(9, 9) # cyclic
seq = seq + seq[:8]   # extended to max
print(''.join(map(lambda n: chr(49+n), seq)))

```

After running for ten minutes, the output is a 387,420,497 digit sequence. This is 9^9 + 8 digits, as expected. (Thank you @PeterTaylor for the +8 tip on the cyclic output.)

---
Tags: code-challenge
---


title: Enumerate an undecidable set

text:
# Question
Title: Enumerate an undecidable set
An undecidable set is a set for which determining whether an object is an element of the set is an undecidable problem

Write a program which runs forever, printing the elements of any undecidable set, each element appearing on its own line. For any element in the set, there must be a finite amount of time after which your program will print that element. Each element should only be printed once.

Since you have to enumerate the elements, the set you choose will be RE.

Some examples of undecidable sets which are RE:

# Answer
> 4 votes
### Haskell, 404 characters

This Haskell program prints all FRACTRAN programs which halt when given the input `2`. (The syntax of a FRACTRAN program is a list of positive rational numbers.)

```
import Data.Ratio
import Data.List
import Data.Either
r=do
 z<-[1..]
 let r=repeat z
 (p,q)<-zip r[1..z]++zip[1..z]r
 if gcd p q==1 then[p%q]else[]
o l=d[map(:xs)r|xs<-l]
e p n=n:maybe[](e p)(find((==1).denominator)$map(*n)p)
h p=map Left(e p 2)++[Right p]
main=mapM print$rights$d$map h$d$iterate o[[]]
d=concat.s
s[]=[]
s([]:b)=s b
s((x:a):b)=[x]:z a(s b)
z[]b=b
z a[]=map(:[])a
z(x:a)(y:b)=(x:y):z a b

```

I have made no great effort to compress this program. Furthermore, the GCD test in the definition of `r` is purely an optimization (it avoids duplicates).

(Also, If you are interested in running it, be sure to compile it, perhaps with optimization; I found that running it in `ghci` quickly consumed gigabytes of memory.)

It operates by successively constructing infinite lists of infinite lists and then flattening them in a diagonal order: the list of all positive rational numbers, the list of all lists of positive rational numbers (all programs), and the list of all evaluation states (including “halted”) of all programs. We then print only the halted states (which are annotated with the program which halted).

Here is the uncompressed and commented version:

```
import Data.Ratio
import Data.List
import Data.Either

-- List of all positive rational numbers
rationals = do
  limit <- [1..]
  let r = repeat limit
  (p,q) <- zip r [1..limit] ++ zip [1..limit] r
  if gcd p q == 1 then [p%q] else []
-- List of all lists of positive rational numbers (all FRACTRAN programs)
programs = diagonal $ iterate oneMore [[]]
oneMore l = diagonal [map (:xs) rationals | xs <- l]

-- FRACTRAN evaluator
evalStep p n = find ((== 1) . denominator) $ map (* n) p
evaluation p n = n : maybe [] (evaluation p) (evalStep p n)
evaluationWithHaltMarker p = map Left (evaluation p 2) ++ [Right p]

-- All evaluation states of all programs
evaluations = diagonal $ map evaluationWithHaltMarker programs

-- All halting programs
haltingPrograms = rights evaluations

main = mapM_ print haltingPrograms

-- from http://stackoverflow.com/questions/7141287/haskell-cartesian-product-of-infinite-lists
diagonal :: [[a]] -> [a]
diagonal = concat . stripe
    where
    stripe [] = []
    stripe ([]:xss) = stripe xss
    stripe ((x:xs):xss) = [x] : zipCons xs (stripe xss)

    zipCons [] ys = ys
    zipCons xs [] = map (:[]) xs
    zipCons (x:xs) (y:ys) = (x:y) : zipCons xs ys

```

The `Left` values are never actually looked at since we don't care about non-halting states; it's just the shortest way I saw to carry through the incremental evaluation.

Some “future work” if one were trying to write a practical implementation to generate interesting programs, rather than golfing, would be to reduce the needed work by restricting the set of programs under consideration to those which:

* do not have a statically obvious loop (e.g. an integer).
* are unique under “register renaming”; e.g. \[3/2, 5/3\] is the same as \[7/2, 5/7\].
* have no dead code under the assumption that the input is 2; e.g. in \[5/3, 7/2\], 5/3 is dead code because no 3s are in numerators.
* have no dead code due to preceding code; e.g. in \[3/2, 5/2\], 3/2 will always take precedence over 5/2.

I mention these cases in particular because (other than the looping one) they form the majority of the output. As far as I've run it, it has not produced any output program of length greater than 2.

# Answer
> 1 votes
### Haskell, 232 characters (with line breaks removed)

This Haskell program prints all solvable Post correspondence problems over the alphabet {A, B}. (Actually, it prints only the ones that actually use every tile at least once. But this shouldn't affect the undecidability of the set.) Each set of tiles is sorted (using Haskell's `sort` function; I don't know how that works on lists of tuples of strings, but it does) and de-duplicated (using `nub`), and the entire list of solutions is de-duplicated as well.

It works by generating all strings, and then, for each string and for each number `n` up to twice the length of the string plus one, generating all pairs of ways to break the string into `n` pieces. The `d` function generates all ways to break a string `s` into a number `n` of pieces. The program takes advantage of the fact that in Haskell, `do` notation on lists simulates non-deterministic choice.

(If I'm not mistaken, "twice the length of the string plus one" is the greatest number of distinct tiles a string can serve as a solution string for. For example, "AB" is a solution string for ("","A"), ("","B"), ("A",""), ("B",""), ("","").)

The `sequence` command, as used right after `s <-` (but not as used right after `main =`), returns all ways of selecting one element from each of a list of lists; for example, `sequence ["abc", "123"]` is `["a1", "a2", "a3", "b1", "b2", "b3", "c1", "c2", "c3"]`.

```
import Data.List;
main=sequence.map print.nub$do{
n<-[1..];
s<-sequence$replicate n"AB";
p<-[1..n];
u<-d p (s*2+1);
v<-d p (s*2+1);
return.nub.sort$zip u v
};
d 0""=[[]];
d 0_=[];
d n s=do
f<-[0..length s];
c<-d(n-1)(drop f s);
return(take f s:c)

```

With the line breaks, this is 246 characters, but all of the line breaks can be removed.

---
Tags: code-golf
---


title: Decide Goldbach's conjcture

text:
# Question
Title: Decide Goldbach's conjcture
Your job is to write a program that determines if Goldbach's conjecture is true. The requirements are this:

* If it is true: Print nothing. Run forever.
* If it is false: Print the *first* counterexample. Halt.

Shortest code wins, but show why it works. **Don't use any Prime built-in functions.**

**Edit:** If you want, include another version that just adds a line that prints what even number you've found a solution to help explain your answer. (It should print 2,4,6,...).

**Note:** If the conjecture get proven or disproven conclusively, then this will become irrelevant, and I might change it to some other similar open problem.

# Answer
> 3 votes
# Ruby, 94

```
require'Prime'
(4..1/0.0).step(2){|x|p=Prime.take x
p x if p.product(p).all?{|y|y[0]+y[1]!=x}}

```

VERY VERY slow and inefficient. Finds all possible sums of primes less than the number, *and* recalculates the primes each iteration! :D

Change `.all?` to `.any?` to see all non-counter-examples (?), which is all even numbers \> 2 :P

# Answer
> 2 votes
## Ruby, 85 (incomplete)

I submit this as a partial answer to the question.

The following program will run until it determines that Goldbach's conjecture is solved. It will then exit and print nothing. I have not yet coded the counterexample-printing in the case of falseness.

```
require'open-uri'
while/Goldbach's conjecture/=~open('http://goo.gl/fuJLr1').read;end

```

Please enjoy. **:-)**

# Answer
> 0 votes
# Befunge - 0

Works up until the 4 * 1018 iteration of the loop; after that, I am not sure:

Okay, okay; here is a valid **Python** solution (236 chars):

```
import sys
def p(a):
 for i in g():
    if a%i!=0:return 0
 return 1
def g():x=2;while 1:x+=1;yield x
for i in g():
 for x in g():
    for y in g():
     if y+x>i:break;if p(x)*p(y):x=i+1
    if x-i:print i;sys.exit()
    if x>=i:break;

```

---
Tags: code-golf
---


title: Give a multiple choice test

text:
# Question
Title: Give a multiple choice test
I present to you a test! Your test is to test. The test is to test the testee with tests a tester gives you, in the shor**test** amount of code. Specifically, you will give a multiple choice test that you have recieved as input.

In this challenge, you must take an input like this:

```
1. Our site is called Programming Puzzles & Code ________.
A: Debugging
*B: Golf
C: Hockey
D: Programming
2. What is the *most* popular tag on our site?
A: [debug]
B: [program]
*C: [code-golf]
D: [number]
E: [c++]
3. We are part of the ________ Exchange network.
*A: Stack
B: Code
C: Programmer
D: Hockey
4. Is this the first question?
A: Yes
*B: No
5. Is this the last question?
*A: Yes
B: No

```

And here is an example of the test being taken:

```
1. Our site is called Programming Puzzles & Code ________.
A: Debugging
B: Golf
C: Hockey
D: Programming
answer: B
correct!

2. What is the *most* popular tag on our site?
A: [debug]
B: [program]
C: [code-golf]
D: [number]
E: [c++]
answer: C
correct!

3. We are part of the ________ Exchange network.
A: Stack
B: Code
C: Programmer
D: Hockey
answer: B
incorrect! the answer was A

4. Is this the first question?
A: Yes
B: No
answer: B
correct!

5. Is this the last question?
A: Yes
B: No
answer: B
incorrect! the answer was A

overview:
3 correct, 2 incorrect (60%)

3. We are part of the ________ Exchange network.
you chose B: Code
the answer was A: Stack

5. Is this the last question?
you chose B: No
the answer was A: Yes

```

Formal specification:

* Input
    + If a line begins with a number followed by a dot and a space, it is a question with that number. Numbers will always start from 1 and go up 1 each question.
    + If a line begins with an optional asterisk, a letter, a colon, and then a space, it is an answer. Answers will also always be sequential. There will be only one correct answer per question.
    + A line will not begin in any other way than the previously mentioned ways.
    + Input may be accepted in any way (reading from a file, stdin, etc.) but must not be hardcoded into your program.
* Output (test-taking phase)
    + First, print out each question sequentially. Print the question and its answers as recieved in input, but do not print the asterisk indicating correct answers.
    + Then, print a newline and `"answer: "`. Wait for user input. User input will always correspond to an answer.
    + If the correct answer (the one with an asterisk) is the same as the one the user input, output `"correct!"`. Otherwise, output `"incorrect! the answer was " + correct_letter`.
    + Separate each question with a blank line, then repeat the previous output steps until there are no more questions.
* Output (overview phase)
    + Print `"overview: "` and then a newline.
    + Print `"{number of correct answers} correct, {incorrect answers} incorrect ({percent correct, rounded to the nearest whole number}%)"` (of course substituting the phrases in curly braces with their respective values). Then print a blank line for spacing.
    + Now, for each question that was wrong, print the question (not its answers), then on a new line `"you chose " + answer_you_chose`, and on another line `"the answer was " + correct_answer`. Separate each wrong answer's overview with a blank line.
* In order to reduce cheating by interpreting things literally, when given the same output here, and the same input in the test-taking phase, your program must output exactly the same thing as the sample output.

This is ; shortest code wins! (And gets an A+ (green checkmark)!)

# Answer
## Perl 5, 279

```
$y=correct;@w=(the,$n=answer,was);map{s/^\*((.+?):.+)/$a=$1/me;print"$_$n: ";chop($@=<>);print$@eq($l=$2)?++$d&&"$y!

":(/^\d.+/,$o.=$&,/^$@.+/m,$o.="
you chose: $&
@w $a

")&&"in$y! @w $l

"}@_=split/(?=^\d)/m,join"",<>;printf"overview:
$d $y, %d in$y (%d%)

$o",@_-$d,$d/@_*100

```

*Note: The newlines are required for output formatting.*

Every time I think I can't golf it any more, I learn something new! It's slowly becoming more punctuation than legible text... I think that's a good thing?

Usage: `perl -e '...' test.txt` or `perl test.pl test.txt`.

If you choose an option not presented in the list, you will get incorrect output in the overview (it will say `you chose: 1. Our site is called Programming Puzzles & Code ________.` for example).

Example run
> 2 votes

# Answer
# Mathematica 144

This may be an invalid attempt. I separated the question from each answer in the input. I also indicated the correct answer by a letter in a separate field, rather than an asterisk before the alternative.

Anyway...

**The Data**

```
questions={{{"\n1. Our site is called Programming Puzzles & Code ________.\n","A: Bugging\n","B: Golf\n","C: Hockey\n","D: Programming\n"},"B"},{{"\n2. What is the most popular tag on our site? \n","A: [debug]\n","B: [program]\n","C: [code golf]\n","D: [number]\n"},"C"},{{"\n3. We are part of the _______ Exchange network. \n","A: Stack\n","B: Code\n","C: Programmer\n","D: Hockey\n"},"A"},{{"\n4. Is this the first question? \n","A: Yes\n","B: No\n"},"B"},{{"\n5. Is this the last question? \n","A: Yes\n","B: No\n"},"A"}};

```

**Code**

An answer to each question is entered through a dialog box. Questions, answers, and feedback are printed.

```
f@x_:=
Print[If[((r=ChoiceDialog[Print[""<>#,"\nanswer: "];""<>#,StringTake[Rest@#,1]])==#2),
r<>"\ncorrect!", r<>"\nincorrect, the answer is "<>#2]&@@x]

```

**Test**

```
f /@ questions

```
> 3 votes

# Answer
**Java - 1210**

```
int i,o;String q;String[]s={"1. Our site is called Programming Puzzles & Code ________.\n","2. What is the most popular tag on our site?\n","3. We are part of the ________ Exchange network.\n","4. Is this the first question?\n","5. Is this the last question?\n"},b={"B","C","A","B","A"},p=new String[5];String[][]a={{"A: Debugging\n","B: Golf\n","C: Hockey\n","D: Programming\n","answer: "},{"A: [debug]\n","B: [program]\n","C: [code-golf]\n","D: [number]\n","E: [c++]\n","answer: "},{"A: Stack\n","B: Code\n","C: Programmer\n","D: Hockey\n","answer: "},{"A: Yes\n","B: No\n","answer: "},{"A: Yes\n","B: No\n","answer: "}};java.util.Map<String,Integer>m=new java.util.HashMap(){{put("A",0);put("B",1);put("C",2);put("D",3);put("E",4);}};java.util.Scanner u=new java.util.Scanner(System.in);for(i=0;i<5;i++){q=s[i];for(o=0;o<a[i].length;)q+=a[i][o++];System.out.print(q);if(b[i].equals(p[i]=u.nextLine()))q="correct!";else q="incorrect! the answer was "+b[i];System.out.println(q+"\n");}q="";o=0;for(i=0;i<5;i++)if(b[i].equals(p[i]))o++;else q+=s[i]+"you chose "+a[i][m.get(p[i])]+"the answer was "+a[i][m.get(b[i])]+"\n";System.out.println("overview:\n"+o+" correct, "+(5-o)+" incorrect ("+o*100/5+"%)\n\n"+q);

```

formatted: 1980

```
String[] s = {"1. Our site is called Programming Puzzles & Code ________.\n",
        "2. What is the most popular tag on our site?\n",
        "3. We are part of the ________ Exchange network.\n",
        "4. Is this the first question?\n",
        "5. Is this the last question?\n"};
    String[][] a = {
        {"A: Debugging\n", "B: Golf\n", "C: Hockey\n", "D: Programming\n", "answer: "},
        {"A: [debug]\n", "B: [program]\n", "C: [code-golf]\n", "D: [number]\n", "E: [c++]\n", "answer: "},
        {"A: Stack\n", "B: Code\n", "C: Programmer\n", "D: Hockey\n", "answer: "},
        {"A: Yes\n", "B: No\n", "answer: "},
        {"A: Yes\n", "B: No\n", "answer: "}};

    java.util.Map<String, Integer> m = new java.util.HashMap<String, Integer>() {
        {
            put("A", 0);
            put("B", 1);
            put("C", 2);
            put("D", 3);
            put("E", 4);
        }
    };
    String[] b = {"B", "C", "A", "B", "A"};
    String[] p = new String[5];
    java.util.Scanner u = new java.util.Scanner(System.in);
    String q;
    int i;
    int o;
    for (i = 0; i < 5; i++) {
        q = s[i];
        for (o = 0; o < a[i].length;) {
            q += a[i][o++];
        }
        System.out.print(q);
        if (b[i].equals(p[i] = u.nextLine())) {
            q = "correct!";
        } else {
            q = "incorrect! the answer was " + b[i];
        }
        System.out.println(q + "\n");
    }
    q = "";
    o = 0;
    for (i = 0; i < 5; i++) {
        if (b[i].equals(p[i])) {
            o++;
        } else {
            q += s[i] + "you chose " + a[i][m.get(p[i])] + "the answer was " + a[i][m.get(b[i])] + "\n";
        }
    }
    System.out.println("overview:\n" + " correct, " + (5 - o) + " incorrect (" + o * 100 / 5 + "%)\n\n" + q);

```

This certainly won’t be the shortest but it is all self-contained
> 2 votes

# Answer
## Haskell, 598

```
import System.Environment
import System.IO
n=putStrLn
p=putStr
d#s=p$show d++s
v&(m:a)=n m>>q[]""a>>= \(r,(s,t))->n s>>n"">>b v m t&r
(r,w,s)&[]=n"overview:">>r#" correct, ">>w#" incorrect (">>((100*r)`div`(r+w))#"%)\n">>mapM_ n s
b(r,w,s)m t|null t=(r+1,w,s)|1<3=(r,w+1,s++"":m:t)
q u c(('*':a):r)=q u a(a:r)
q u c(a@(o:':':_):r)=n a>>q(([o],a):u)c r
q u c r=p"answer: ">>hFlush stdout>>(\i->(r,a(maybe i id$lookup i u)c))`fmap`getLine
a j c|j==c=("correct!",[])|1<3=("incorrect! the answer was "++[head c],["you choose "++j,"the answer was "++c])
main=getArgs>>=readFile.head>>=((0,0,[])&).lines

```

Way longer than I'd like. It's set wiki so have at it!

Alas, we lose 32 characters to flushing stdout. Another 38 characters could be saved if the test script were read from a fixed file named "t" rather than specified on the command line.

When run on the input given in the question:

```
& runhaskell 15961-Tester.hs 15961-test.txt
1. Our site is called Programming Puzzles & Code ________.
A: Debugging
B: Golf
C: Hockey
D: Programming
answer: B
correct!

2. What is the *most* popular tag on our site?
A: [debug]
B: [program]
C: [code-golf]
D: [number]
E: [c++]
answer: C
correct!

3. We are part of the ________ Exchange network.
A: Stack
B: Code
C: Programmer
D: Hockey
answer: B
incorrect! the answer was A

4. Is this the first question?
A: Yes
B: No
answer: B
correct!

5. Is this the last question?
A: Yes
B: No
answer: B
incorrect! the answer was A

overview:
3 correct, 2 incorrect (60%)

3. We are part of the ________ Exchange network.
you choose B: Code
the answer was A: Stack

5. Is this the last question?
you choose B: No
the answer was A: Yes

```
> 0 votes

---
Tags: code-golf
---


title: Christmas quine!

text:
# Question
Title: Christmas quine!
In the language of your choice, write a program that is arranged in the shape of a Christmas tree that prints itself in the same shape.

What is not allowed:

* Printing out the source file
* Code that is nothing but statements that get echoed by an interpreter by virtue of them being literals (eg just using a tree-shaped tower of lists in python)

# Answer
## JavaScript

The 'star' might be a bit too large for the tree...

```
        (function _()
     {return('        (')
      +(''+''+''+''+'')
             +_+
            ')()'
           ;'We w'
          +'wis'+0+
         'h you a '
        +0+'merry Ch'
       +'ristmas, '+0+
      +'we '+0+'wish y'
     +0+'ou a merry Chr'
    +'istmas, we w'+0+'i'
   +0+'sh you '+0+'a merr'
  +'y Christmas and a h'+0+
 +'appy'+0+'new year! Ho ho'
+0+' ho! Merry '+0+'Christma'
            +'s!'
            })()

```

The zeroes are baubles and look best in the editor:
> 16 votes

# Answer
# Ruby

You never said we couldn't use network access... :D

```
        #
       s="
      open(
     'http:/
    /pastebin
   .com/raw.ph
  p?i=mGzbahp5'
 ).read";s=eval(
s.gsub! /\s/,'');
      puts(
      s+'')

```

Outputs itself verbatim.

Yes, I could have used a URL shortener, but that would have made it less obvious and amusing :P Also I needed *something* to take up space; otherwise the tree would be tiny.

Execute like this:

```
ruby -ropen-uri christmasquine.rb

```
> 9 votes

# Answer
# perl

```
#!/usr/bin/perl
$_=<<'the source';eval $_;

          #
         #*#
        print
       "#!/u".
      "sr/bin".
     "/perl \n".
    "\$_=<<'the".
   " source';eva".
  "l \$_;\n${_}th".
 "e source\n";# Mery
#Christmas to all !!!
         ###
         ###
         #*#

the source

```
> 4 votes

# Answer
Here's a tiny one in **GolfScript**:

```
   {
  ".~
 "2/~\
+@@2$*}.
   ~

```

Note that the code above includes two space characters at the end of the second line from the top; those spaces are essential for correct operation. Also, the code should be saved using Unix-style (`LF`) linefeeds, not Windows-style `CR`+`LF`.

---

Here's a slightly bigger (and less whitespace-sensitive) one, including a festive message:

```
     {
    " "
   MERRY
  5*n\+\n
 CHRISTMAS
".~"+2$*1>}
     .
     ~

```

A mildly interesting feature is that the words `MERRY` and `CHRISTMAS` are not string literals, although they *are* no-ops, and are copied to the output along with the code block surrounding them.
> 4 votes

---
Tags: popularity-contest, ascii-art, quine
---


# Question
Title: Four score and twenty. (Complete Obfuscation)
This challenge is to write a program that prints a great famous speech.

# Goals:

* Obfuscated text (you should not be able to tell what speech it prints without running it)
* Obfuscated code (it is more fun if you cant figure out how it works)
* non-wrapping text and code is preferred. (78 chars/line)
* Low score wins.

# Rules:

1. When picking a speech it must be famous: it must have at least three published references (newspaper, history book, or similar) websites only count 1/3 unless associated with a dead tree publication. (if only using websites you need 9)
2. When picking a speech it must be great: it must not be too short (5 sentence minimum) or too long (It should be able to be read in less than 15 minutes) and have real meaning (you must assert that you have a strong opinion about the speech)
3. No input (files, web, etc.)

# Scoring:

1. Punctuation and white space has no score.
2. Words found in the speech count 20 points.
3. Words not found in the speech count one point.
4. choice of language:
    * golf languages where the longest command is 1 letter cost 15 points.
    * languages that print to output by default cost 3 points.
    * interpreted languages cost 1 point.
    * java and languages where a typical method call is longer than 20 chars get a -5 point bonus.
5. three free lines of boilerplate (warnings, standard i/o, #!) boilerplate must be generic.

# Answer
## Python

```
import sys, this
sys.stderr.write(''.join(map(lambda i: this.d.get(i, i),
'V nz cebhq gb pbzr gb guvf pvgl nf gur thrfg bs lbhe qvfgvathvfurq Znlbe, jub '
'unf flzobyvmrq guebhtubhg gur jbeyq gur svtugvat fcvevg bs Jrfg Oreyva. Naq V '
'nz cebhq gb ivfvg gur Srqreny Erchoyvp jvgu lbhe qvfgvathvfurq Punapryybe jub '
'sbe fb znal lrnef unf pbzzvggrq Treznal gb qrzbpenpl naq serrqbz naq '
'cebterff, naq gb pbzr urer va gur pbzcnal bs zl sryybj Nzrevpna, Trareny '
'Pynl, jub unf orra va guvf pvgl qhevat vgf terng zbzragf bs pevfvf naq jvyy '
'pbzr ntnva vs rire arrqrq. \n\nGjb gubhfnaq lrnef ntb gur cebhqrfg obnfg jnf '
'"pvivf Ebznahf fhz." Gbqnl, va gur jbeyq bs serrqbz, gur cebhqrfg obnfg vf '
'"Vpu ova rva Oreyvare." \n\nV nccerpvngr zl vagrecergre genafyngvat zl '
'Trezna! \n\nGurer ner znal crbcyr va gur jbeyq jub ernyyl qba\'g haqrefgnaq, '
'be fnl gurl qba\'g, jung vf gur terng vffhr orgjrra gur serr jbeyq naq gur '
'Pbzzhavfg jbeyq. Yrg gurz pbzr gb Oreyva. Gurer ner fbzr jub fnl gung '
'pbzzhavfz vf gur jnir bs gur shgher. Yrg gurz pbzr gb Oreyva. Naq gurer ner '
'fbzr jub fnl va Rhebcr naq ryfrjurer jr pna jbex jvgu gur Pbzzhavfgf. Yrg '
'gurz pbzr gb Oreyva. Naq gurer ner rira n srj jub fnl gung vg vf gehr gung '
'pbzzhavfz vf na rivy flfgrz, ohg vg crezvgf hf gb znxr rpbabzvp cebterff. '
'Ynff\' fvp anpu Oreyva xbzzra. Yrg gurz pbzr gb Oreyva. \n\nSerrqbz unf znal '
'qvssvphygvrf naq qrzbpenpl vf abg cresrpg, ohg jr unir arire unq gb chg n '
'jnyy hc gb xrrc bhe crbcyr va, gb cerirag gurz sebz yrnivat hf. V jnag gb '
'fnl, ba orunys bs zl pbhagelzra, jub yvir znal zvyrf njnl ba gur bgure fvqr '
'bs gur Ngynagvp, jub ner sne qvfgnag sebz lbh, gung gurl gnxr gur terngrfg '
'cevqr gung gurl unir orra noyr gb funer jvgu lbh, rira sebz n qvfgnapr, gur '
'fgbel bs gur ynfg 18 lrnef. V xabj bs ab gbja, ab pvgl, gung unf orra '
'orfvrtrq sbe 18 lrnef gung fgvyy yvirf jvgu gur ivgnyvgl naq gur sbepr, naq '
'gur ubcr naq gur qrgrezvangvba bs gur pvgl bs Jrfg Oreyva. Juvyr gur jnyy vf '
'gur zbfg boivbhf naq ivivq qrzbafgengvba bs gur snvyherf bs. gur Pbzzhavfg '
'flfgrz, sbe nyy gur jbeyq gb frr, jr gnxr ab fngvfsnpgvba va vg, sbe vg vf, '
'nf lbhe Znlbe unf fnvq, na bssrafr abg bayl ntnvafg uvfgbel ohg na bssrafr '
'ntnvafg uhznavgl, frcnengvat snzvyvrf, qvivqvat uhfonaqf naq jvirf naq '
'oebguref naq fvfgref, naq qvivqvat n crbcyr jub jvfu gb or wbvarq gbtrgure. '
'\n\nJung vf gehr bs guvf pvgl vf gehr bs Treznal\xe2\x80\x94erny, ynfgvat '
'crnpr va Rhebcr pna arire or nffherq nf ybat nf bar Trezna bhg bs sbhe vf '
'qravrq gur ryrzragnel evtug bs serr zra, naq gung vf gb znxr n serr pubvpr. '
'Va 18 lrnef bs crnpr naq tbbq snvgu, guvf trarengvba bs Treznaf unf rnearq '
'gur evtug gb or serr, vapyhqvat gur evtug gb havgr gurve snzvyvrf naq gurve '
'angvba va ynfgvat crnpr, jvgu tbbq jvyy gb nyy crbcyr. Lbh yvir va n qrsraqrq '
'vfynaq bs serrqbz, ohg lbhe yvsr vf cneg bs gur znva. Fb yrg zr nfx lbh, nf V '
'pybfr, gb yvsg lbhe rlrf orlbaq gur qnatref bs gbqnl, gb gur ubcrf bs '
'gbzbeebj, orlbaq gur serrqbz zreryl bs guvf pvgl bs Oreyva, be lbhe pbhagel '
'bs Treznal, gb gur nqinapr bs serrqbz rireljurer, orlbaq gur jnyy gb gur qnl '
'bs crnpr jvgu whfgvpr, orlbaq lbhefryirf naq bhefryirf gb nyy znaxvaq. '
'\n\nSerrqbz vf vaqvivfvoyr, naq jura bar zna vf rafynirq, nyy ner abg serr. '
'Jura nyy ner serr, gura jr pna ybbx sbejneq gb gung qnl jura guvf pvgl jvyy '
'or wbvarq nf bar naq guvf pbhagel naq guvf terng Pbagvarag bs Rhebcr va n '
'crnprshy naq ubcrshy tybor. Jura gung qnl svanyyl pbzrf, nf vg jvyy, gur '
'crbcyr bs Jrfg Oreyva pna gnxr fbore fngvfsnpgvba va gur snpg gung gurl jrer '
'va gur sebag yvarf sbe nyzbfg gjb qrpnqrf. \n\nNyy serr zra, jurerire gurl '
'znl yvir, ner pvgvmraf bs Oreyva, naq, gurersber, nf n serr zna, V gnxr cevqr '
'va gur jbeqf "Vpu ova rva Oreyvare!"')))

```

This should be run with

```
$ python codegolf.py > /dev/null

```

I guess the text is pretty obfuscated, and the code as well, if you didn't take a closer look into the `this` module. Instead of 78 chars, I stuck to 80.

### Score:

**Language choice:**

Interpreted language: 1

**Code words:**

The words found in the speech are `this` (1x), `for` (1x) but I guess they don't really count since they are language keywords (?).

If they count, this is 29. Otherwise, it's 11.

**Encoded speech words:**

I guess I have a disadvantage here due to picking a long speech. But it has a total of 673 words, none of them in the speech.

**Total score:**

*Best case (Not counting language keywords and encoded speech words):*

1 + 11 = 12

*Worst case (Counting language keywords and encoded speech words):*

1 + 29 + 673 = 703

*Note: Speech is used from here.*
> 4 votes

---
Tags: code-challenge, obfuscation
---


title: Build a snowman!

text:
# Question
Title: Build a snowman!
It's getting to be that time of year, and I figured I might as well post the first winter-themed question :)

Your challenge is to **build a snowman.**

How, you ask? Well, you decide! You can do ASCII art, you can animate it, you can golf the code, you can make the code that generates the snowman itself a snowman, you can generate a colored image; be creative!

This is a , so the answer with the most upvotes at the end of December will win. (If an answer surpasses the winner in upvotes, then it will become the new winner.) The winning answer will get the magical green check mark!

# Answer
> 13 votes
**JavaScript/HTML: 454 Characters**

Thanks @Doorknob for the idea

*Snowman Sitting in the Snow*

Here it is running: http://jsfiddle.net/au35H/1/

Code-golfed:

```
<html><head><script>(function(){for(var f=[".",",","*"," "," "],e=["☃",2],n=[16,8],t=[],r,u,i=0;i<n[1];i++){for(r=[],u=0;u<n[0];u++)r.push(" ");t.push(r)}setInterval(function(){for(var r=[],u=[],i=0;i<n[1];i++)r.push(t[i].join(""));for(document.body.innerHTML=r.join("\n"),i=0;i<n[0];i++)u.push(f[Math.floor(Math.random()*f.length)]);t.pop(),t.splice(0,0,u),t[n[1]-1][e[1]]=e[0]},500)})();</script><body style="font:80px monospace;white-space:pre">

```

# Answer
> 11 votes
I just *know* someone is going to post this eventually, so **1 character** in HTML:

(That's a Unicode snowman; U+2603)

It's pretty hard to see, so here's **23 characters**:

```
<p style=font-size:99>☃

```

Renders as this on my browser:

Or, I could be evil and use the deprecated and terrible `font` tag for **15 characters**:

```
<font size=99>☃

```

It renders smaller for some reason.

(of course, these HTML files aren't valid, but latest Chrome (31.0.1650.57 as of writing) gladly accepts them)

# Answer
> 11 votes
Polyglot, 1 character

```
8

```

Sorry.

# Answer
> 8 votes
## MSBuild

Save the following project file as **snowman**:

```
<Project xmlns="http://schemas.microsoft.com/developer/msbuild/2003" DefaultTargets="x">
  <Target Name="x">
    <Exec Command="start http://unicodesnowmanforyou.com"/>
  </Target>
</Project>

```

The task was to *build* a snowman, so:

```
msbuild snowman

```

# Answer
> 8 votes
This is a bit of a cheat as it is mostly reusing some existing code, but it's a slightly modified version of a C++ AMP realtime GPU path tracer I wrote.

Most of the interesting code is here but there's some utility code in a couple of other files for setting up D3D, setting up the window etc.

```
#include "app.h"

#include "d3d11device.h"

#include <vector>
#include <fstream>
#include <chrono>
#include <iostream>
#include <initializer_list>
#include <random>
#include <cassert>
#include <cmath>

#include <amp.h>
#include <amp_graphics.h>

#include <Xinput.h>

#include <amputils.h>

using namespace std;
using namespace renderer;
using namespace concurrency;
using namespace concurrency::direct3d;
using namespace concurrency::graphics;
using namespace concurrency::graphics::direct3d;
using namespace concurrency::fast_math;
using namespace DirectX;
using namespace amputils;

namespace {

template<typename T, size_t N>
size_t ArraySize(T (&)[N]) {
    return N;
}

vector<char> LoadFile(const char* filename) {
    ifstream file(filename, ios_base::binary);
    return vector<char>(istreambuf_iterator<char>(file), (istreambuf_iterator<char>()));
}

struct SimpleVertex
{
    float x, y, z;
};

class Sphere
{
public:
    Sphere(const Vector3& center_, float radius_) restrict(amp, cpu) : center(center_), radius(radius_) {}

    Vector3 GetCenter() const restrict(amp, cpu) { return center; }
    float GetRadius() const restrict(amp, cpu) { return radius; }

    // Used for sampling a light from a point
    Vector3 Sample(const Vector3& p, float u1, float u2, Vector3& normal) const restrict(amp, cpu);

    float Pdf(const Vector3& p, const Vector3& /*wi*/) const restrict(amp, cpu) {
        Vector3 pToCenter = center - p;
        float sinThetaMax2 = radius * radius / Dot(pToCenter, pToCenter);
        float cosThetaMax = sqrt(max(0.1f, 1.f - sinThetaMax2));
        return UniformConePdf(cosThetaMax);
    }

private:
    Vector3 center;
    float radius;
};

class DifferentialGeometry
{
public:
    DifferentialGeometry() restrict(amp, cpu) : p(0.0f), n(0.0f) {}
    DifferentialGeometry(const Vector3& p_, const Vector3& n_) restrict(amp, cpu) : p(p_), n(n_) {}

    const Vector3& GetPoint() const restrict(amp, cpu) { return p; }
    const Vector3& GetNormal() const restrict(amp, cpu) { return n; }

private:
    Vector3 p;
    Vector3 n;
};

bool IntersectP(const Ray& ray, const Sphere& sphere, float& t) restrict(amp, cpu)
{
    const auto v = ray.GetOrigin() - sphere.GetCenter();
    const auto a = Dot(ray.GetDirection(), ray.GetDirection());
    const auto minusB = -2.f * Dot(ray.GetDirection(), v);
    const auto c = Dot(v, v) - Square(sphere.GetRadius());
    const auto discrim = (Square(minusB) - 4.f * a * c);
    if (discrim < 0.f) {
        return false;
    }

    const auto sqrtDiscrim = sqrt(discrim);
    const auto tMax = minusB + sqrtDiscrim;
    if (tMax < 0.f) {
        return false;
    }

    const auto denominator = 1.f / (2.f * a);
    const auto tMin = minusB - sqrtDiscrim;
    t = (tMin < 0.f ? tMax : tMin) * denominator;
    return true;
}

bool Intersect(const Ray& ray, const Sphere& sphere, float& t, DifferentialGeometry& dg) restrict(amp, cpu)
{
    const auto v = ray.GetOrigin() - sphere.GetCenter();
    const auto a = Dot(ray.GetDirection(), ray.GetDirection());
    const auto minusB = -2.f * Dot(ray.GetDirection(), v);
    const auto c = Dot(v, v) - Square(sphere.GetRadius());
    const auto discrim = (Square(minusB) - 4.f * a * c);
    if (discrim < 0.f) {
        return false;
    }

    const auto sqrtDiscrim = sqrt(discrim);
    const auto tMax = minusB + sqrtDiscrim;
    if (tMax < 0.f) {
        return false;
    }

    const auto denominator = 1.f / (2.f * a);
    const auto tMin = minusB - sqrtDiscrim;
    t = (tMin < 0.f ? tMax : tMin) * denominator;
    Vector3 p = ray(t);
    dg = DifferentialGeometry(p, Normalize(p - sphere.GetCenter()));
    return true;
}

inline Vector3 Sphere::Sample(const Vector3& p, float u1, float u2, Vector3& normal) const restrict(amp, cpu) {
    Vector3 pToCenter = center - p;
    Vector3 wc = Normalize(pToCenter);
    Vector3 wcX(0.0f), wcY(0.0f);
    CoordinateSystem(wc, wcX, wcY);
    float sinThetaMax2 = radius * radius / Dot(pToCenter, pToCenter);
    float cosThetaMax = sqrt(max(0.1f, 1.f - sinThetaMax2));
    float tHit;
    DifferentialGeometry dg;
    Ray r(p, UniformSampleCone(u1, u2, cosThetaMax, wcX, wcY, wc));
    if (!Intersect(r, *this, tHit, dg))
        tHit = Dot(pToCenter, Normalize(r.GetDirection()));
    normal = dg.GetNormal();
    return dg.GetPoint();
}

class Primitive
{
public:
    Primitive(const Sphere& s_, const Vector3& color_) restrict(amp, cpu) : s(s_), color(color_) {}

    const Sphere& GetSphere() const restrict(amp, cpu) { return s; }
    const Vector3& GetColor() const restrict(amp, cpu) { return color; }

private:
    Sphere s;
    Vector3 color;
};

struct CameraSample
{
    CameraSample(float x_, float y_) restrict(amp, cpu) : x(x_), y(y_) {}
    float x, y;
};

class StratifiedSampler
{
public:
    explicit StratifiedSampler(int n) restrict(amp, cpu) : mN(n) {}

    int GetNumSamples() const restrict(amp, cpu) { return mN * mN; }
    CameraSample Sample2D(amputils::Rng& rng, int i) restrict(amp, cpu) {
        float dxy = 1.0f / mN;
        float xOff = static_cast<float>(i % mN);
        float yOff = static_cast<float>(i / mN);
        return CameraSample((xOff + rng.GetUniform()) * dxy, (yOff + rng.GetUniform()) * dxy);
    }

private:
    StratifiedSampler& operator=(const StratifiedSampler&);

    int mN;
};

class Camera
{
public:
    Camera(int filmWidth, int filmHeight)
        : mPos(0.0f, 0.0f, -20.0f),
          mYaw(0.0f),
          mPitch(0.0f),
          mWorldToCamera(XMMatrixLookAtLH(XMVectorReplicate(0.0f), XMVectorReplicate(1.0f), XMVectorSet(0.0f, 1.0f, 0.0f, 0.0f))),
          mCameraToWorld(XMMatrixInverse(nullptr, mWorldToCamera.GetXMMATRIX())),
          mProjection(XMMatrixPerspectiveFovLH(3.1415f * 0.333f, 1.0f, 1e-2f, 1e3f)),
          mInverseProjection(XMMatrixInverse(nullptr, mProjection.GetXMMATRIX())),
          mFilmWidth(filmWidth),
          mFilmHeight(filmHeight)
    {
        UpdateMatrices();
    }

    const Matrix4& GetWorldToCamera() const restrict(amp, cpu) { return mWorldToCamera; }
    const Matrix4& GetCameraToWorld() const restrict(amp, cpu) { return mCameraToWorld; }
    const Matrix4& GetProjection() const restrict(amp, cpu) { return mProjection; }
    const Matrix4& GetInverseProjection() const restrict(amp, cpu) { return mInverseProjection; }

    void RotateCam(float yaw, float pitch)
    {
        mYaw += yaw;
        mPitch = Clamp(mPitch + pitch, 3.14f * -0.45f, 3.14f * 0.45f);
        UpdateMatrices();
    }

    void TranslateCam(const Vector3& trans)
    {
        mPos += trans;
        UpdateMatrices();
    }

    Ray GenerateRay(int x, int y, int i, StratifiedSampler& samp, amputils::Rng& rng) const restrict(amp, cpu) {
        auto camSamp = samp.Sample2D(rng, i);
        const float fx = (camSamp.x + float(x)) / float(mFilmWidth);
        const float fy = (camSamp.y + float(y)) / float(mFilmHeight);
        const Vector4 rayFilm(2.0f * fx - 1.0f, 2.0f * fy - 1.0f, 0.0f, 1.0f);
        const Vector4 rayFilmCam = Project(rayFilm, GetInverseProjection());
        const Vector4 rayFilmWorld = Transform(rayFilmCam, GetCameraToWorld());
        const Vector4 rayStartWorld(mPos.x(), mPos.y(), mPos.z(), 1.0f);
        const Vector4 rayDirection(rayFilmWorld - rayStartWorld);
        return Ray(Vector3(rayStartWorld.e(0), rayStartWorld.e(1), rayStartWorld.e(2)), Vector3(rayDirection.e(0), rayDirection.e(1), rayDirection.e(2)));
    }

private:
    void UpdateMatrices()
    {
        XMMATRIX cam = XMMatrixLookAtLH(XMVectorSet(mPos.x(), mPos.y(), mPos.z(), 1.0f), XMVectorSet(mPos.x(), mPos.y(), mPos.z() + 1.0f, 1.0f), XMVectorSet(0.0f, 1.0f, 0.0f, 0.0f));
        XMMATRIX rot = XMMatrixMultiply(XMMatrixRotationY(mYaw), XMMatrixRotationX(mPitch));
        mWorldToCamera = XMMatrixMultiply(cam, rot);
        mCameraToWorld = XMMatrixInverse(nullptr, mWorldToCamera.GetXMMATRIX());
    }

    Vector3 mPos;
    float mYaw, mPitch;

    Matrix4 mWorldToCamera;
    Matrix4 mCameraToWorld;
    Matrix4 mProjection;
    Matrix4 mInverseProjection;

    int mFilmWidth, mFilmHeight;
};

class Scene;

class SceneView
{
public:
    int GetNumPrims() const restrict(amp, cpu) { return prims.extent.size(); }
    const Primitive& GetPrim(int i) const restrict(amp, cpu) { return prims[i]; }

    const Camera& GetCamera() const restrict(amp, cpu) { return camera; }

    const Primitive& GetLight() const restrict(amp, cpu) { return light; }

private:
    friend class Scene;
    explicit SceneView(const Camera& camera_, const vector<Primitive>& prims_, const Primitive& light_)
        : camera(camera_),
          prims(prims_.size(), prims_),
          light(light_)
    {
    }

    Camera camera;
    array_view<const Primitive> prims;
    Primitive light;
};

class Scene
{
public:
    explicit Scene(int filmWidth, int filmHeight, const initializer_list<Primitive>& prims_)
        : camera(filmWidth, filmHeight),
          prims(prims_.begin(), prims_.end()),
          light(Sphere(Vector3(50.0f, 50.0f, -50.0f), 5.0f), Vector3(0.75f, 0.75f, 0.67f))
    {
    }

    SceneView GetView() const
    {
        return SceneView(camera, prims, light);
    }

    Camera& GetCamera() { return camera; }
    const Camera& GetCamera() const { return camera; }

    const Primitive& GetLight() const { return light; }

    Primitive& GetPrimitive(int i) { return prims[i]; }

private:
    Camera camera;
    vector<Primitive> prims;
    Primitive light;
};

}

Scene MakeScene(int filmWidth, int filmHeight)
{
    auto prims = {
        Primitive(Sphere(Vector3(0.0f, 0.0f, 1100.0f), 1000.0f), Vector3(0.61f, 0.78f, 1.0f)),
        Primitive(Sphere(Vector3(0.0f, -1010.0f, 0.0f), 1000.0f), Vector3(0.85f, 0.85f, 0.85f)),
        Primitive(Sphere(Vector3(-2.0f, -6.5f, 2.0f), 4.0f), Vector3(0.85f, 0.85f, 0.85f)),
        Primitive(Sphere(Vector3(-2.0f, -1.5f, 2.0f), 3.0f), Vector3(0.85f, 0.85f, 0.85f)),
        Primitive(Sphere(Vector3(-2.0f, 2.8f, 2.0f), 2.0f), Vector3(0.85f, 0.85f, 0.85f)),
        Primitive(Sphere(Vector3(-2.0f, 2.8f, 0.0f), 0.2f), Vector3(0.05f, 0.05f, 0.05f)),
        Primitive(Sphere(Vector3(-2.5f, 3.5f, 0.3f), 0.2f), Vector3(0.05f, 0.05f, 0.05f)),
        Primitive(Sphere(Vector3(-1.5f, 3.5f, 0.3f), 0.2f), Vector3(0.05f, 0.05f, 0.05f))
    };
    return Scene(filmWidth, filmHeight, prims);
}

class App : public IApp {
public:
    App(void* hwnd, int width, int height);
    ~App();
    void Update(bool mouseButtons[2], int mouseX, int mouseY) override;

private:
    void UpdateControllerState();
    void UpdateTexture(unsigned t);

    Device mDevice;

    // No copy or assignment
    App(const App&);
    App operator=(const App&);

    ID3D11VertexShaderPtr mVs;
    ID3D11PixelShaderPtr mPs;

    accelerator_view mAcceleratorView;
    texture<float_4, 2> mAmpTex;
    ID3D11Texture2DPtr mD3dTex;
    ID3D11ShaderResourceViewPtr mTexView;
    ID3D11SamplerStatePtr mSamplerState;
    ID3D11InputLayoutPtr mInputLayout;
    ID3D11BufferPtr mQuadVertexBuffer;
    ID3D11BufferPtr mQuadIndexBuffer;

    chrono::time_point<chrono::high_resolution_clock> mLastFrameTime;

    Scene mScene;

    XINPUT_STATE mControllerState;

    vector<amputils::Rng::SeedValue> mRngSeeds;
};

App::App(void* hwnd, int width, int height) :
    mDevice(hwnd, width, height),
    mAcceleratorView(create_accelerator_view(mDevice.GetD3D11Device())),
    mAmpTex(width, height, mAcceleratorView),
    mD3dTex(get_texture(mAmpTex)),
    mLastFrameTime(chrono::high_resolution_clock::now()),
    mScene(MakeScene(width, height)),
    mRngSeeds(mAmpTex.extent.size())
{
    auto vs = LoadFile("simplevs.cso");
    mDevice.GetD3D11Device()->CreateVertexShader(vs.data(), vs.size(), nullptr, &mVs);

    auto ps = LoadFile("simpleps.cso");
    mDevice.GetD3D11Device()->CreatePixelShader(ps.data(), ps.size(), nullptr, &mPs);

    CD3D11_SHADER_RESOURCE_VIEW_DESC resViewDesc(mD3dTex, D3D11_SRV_DIMENSION_TEXTURE2D);
    mDevice.GetD3D11Device()->CreateShaderResourceView(mD3dTex, &resViewDesc, &mTexView);

    CD3D11_SAMPLER_DESC samplerDesc(D3D11_DEFAULT);
    mDevice.GetD3D11Device()->CreateSamplerState(&samplerDesc, &mSamplerState);

    D3D11_INPUT_ELEMENT_DESC elems[] = {
        { "SV_Position", 0, DXGI_FORMAT_R32G32B32_FLOAT, 0, 0, D3D11_INPUT_PER_VERTEX_DATA, 0 }
    };
    mDevice.GetD3D11Device()->CreateInputLayout(elems, ArraySize(elems), vs.data(), vs.size(), &mInputLayout);

    SimpleVertex quadVerts[] = {
        { -1.0f, 1.0f, 0.0f },
        { 1.0f, 1.0f, 0.0f },
        { 1.0f, -1.0f, 0.0f },
        { -1.0f, -1.0f, 0.0f },
    };
    CD3D11_BUFFER_DESC vbDesc(sizeof(quadVerts), D3D11_BIND_VERTEX_BUFFER);
    D3D11_SUBRESOURCE_DATA vbData = { quadVerts, 0, 0 };
    mDevice.GetD3D11Device()->CreateBuffer(&vbDesc, &vbData, &mQuadVertexBuffer);

    uint16_t quadIndices[] = { 0, 1, 2, 2, 3, 0 };
    CD3D11_BUFFER_DESC ibDesc(sizeof(quadIndices), D3D11_BIND_INDEX_BUFFER);
    D3D11_SUBRESOURCE_DATA ibData = { quadIndices, 0, 0 };
    mDevice.GetD3D11Device()->CreateBuffer(&ibDesc, &ibData, &mQuadIndexBuffer);

    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<unsigned int> dis;
    for_each(begin(mRngSeeds), end(mRngSeeds), [&gen, &dis](amputils::Rng::SeedValue& seedValue) {
        seedValue = amputils::Rng::SeedValue(dis(gen), dis(gen), dis(gen), dis(gen));
    });

    amputils::Rng rng(amputils::Rng::SeedValue(dis(gen), dis(gen), dis(gen), dis(gen)));
    StratifiedSampler sampler(4);
    for (int i = 0; i < sampler.GetNumSamples(); ++i) {
        auto samp = sampler.Sample2D(rng, i);
        cout << samp.x << ", " << samp.y << "\n";
    }
}

App::~App() {
}

bool IsShadowed(const Ray& ray, const SceneView& scene) restrict(amp, cpu)
{
    auto lightT = FLT_MAX;
    if (!IntersectP(ray, scene.GetLight().GetSphere(), lightT))
        return true;

    for (auto i = decltype(scene.GetNumPrims())(0); i < scene.GetNumPrims(); ++i)
    {
        const auto& sphere = scene.GetPrim(i).GetSphere();
        float t = FLT_MAX;
        if (IntersectP(ray, sphere, t) && t < lightT) {
            return true;
        }
    }
    return false;
}

template<int RecursionDepth>
inline Vector3 TraceRay(const Ray& ray, const SceneView& scene, Rng& rng, int sampIdx) restrict(amp, cpu)
{
    Vector3 color(0.1f, 0.1f, 0.25f);
    auto nearestT = FLT_MAX;
    DifferentialGeometry nearestDg;
    Vector3 nearestDiffuseColor(0.0f);

    for (auto i = decltype(scene.GetNumPrims())(0); i < scene.GetNumPrims(); ++i)
    {
        const auto& sphere = scene.GetPrim(i).GetSphere();
        float t = FLT_MAX;
        DifferentialGeometry dg;
        if (Intersect(ray, sphere, t, dg) && t < nearestT) {
            nearestT = t;
            nearestDg = dg;
            nearestDiffuseColor = scene.GetPrim(i).GetColor();
        }
    }

    if (nearestT < FLT_MAX) {
        // Direct lighting
        StratifiedSampler sampler(4);
        auto samp = sampler.Sample2D(rng, sampIdx);
        Vector3 lightNormal(0.0f);
        const auto lightPos = scene.GetLight().GetSphere().Sample(nearestDg.GetPoint(), samp.x, samp.y, lightNormal);
        const auto L = Normalize(lightPos - nearestDg.GetPoint());
        if (IsShadowed(Ray(nearestDg.GetPoint() + L * 1e-3f, L), scene))
            color = Vector3(0.0f);
        else
            color = nearestDiffuseColor * Dot(nearestDg.GetNormal(), L) * scene.GetLight().GetColor();

        // Indirect lighting
        auto indirectSamp = sampler.Sample2D(rng, sampIdx);
        auto indirectDirLocal = CosineSampleHemisphere(indirectSamp.x, indirectSamp.y);
        Vector3 normalZ = nearestDg.GetNormal();
        Vector3 normalX(0.0f), normalY(0.0f);
        CoordinateSystem(normalZ, normalX, normalY);
        auto indirectDirWorld = normalX * indirectDirLocal.x() + normalY * indirectDirLocal.y() + normalZ * indirectDirLocal.z();
        Ray indirectRay(nearestDg.GetPoint() + nearestDg.GetNormal() * 1e-3f, indirectDirWorld);
        auto indirectColor = TraceRay<RecursionDepth - 1>(indirectRay, scene, rng, sampIdx) * CosineHemispherePdf(Dot(indirectDirWorld, nearestDg.GetNormal()), 0.0f);
        color += indirectColor * nearestDiffuseColor;
    }

    return color;
}

template<>
inline Vector3 TraceRay<0>(const Ray& /*ray*/, const SceneView& /*scene*/, Rng& /*rng*/, int /*sampIdx*/) restrict(amp, cpu)
{
    return Vector3(0.0f);
}

const int Height = 512;
const int Width = 512;

inline float_4 RaytraceScene(int x, int y, const SceneView& scene, Rng& rng) restrict (amp, cpu)
{
    float_4 totalIrradiance = 0.0f;
    StratifiedSampler sampler(4);
    for (int samp = 0; samp < sampler.GetNumSamples(); ++samp)
    {
        auto ray = scene.GetCamera().GenerateRay(x, y, samp, sampler, rng);
        totalIrradiance += ToFloat4(TraceRay<4>(ray, scene, rng, samp));
    }
    totalIrradiance *= 1.0f / sampler.GetNumSamples();
    return totalIrradiance;
}

void App::UpdateTexture(unsigned t)
{
    auto sceneView = mScene.GetView();
    auto ampTexView = writeonly_texture_view<float_4, 2>(mAmpTex);
    auto rngSeedsView = array_view<const amputils::Rng::SeedValue, 2>(ampTexView.extent, mRngSeeds);
    parallel_for_each(mAcceleratorView, mAmpTex.extent, [ampTexView, sceneView, t, rngSeedsView](index<2> idx) restrict(amp) {
        //Rng::SeedValue rngSeed(rngSeedsView[idx].z1 + t, rngSeedsView[idx].z2 + t, rngSeedsView[idx].z3 + t, rngSeedsView[idx].z4 + t);
        Rng rng(rngSeedsView[idx]);
        ampTexView.set(idx, RaytraceScene(idx[1], idx[0], sceneView, rng));
    });
}

void App::UpdateControllerState()
{
    for (DWORD i = 0; i < 4; ++i)
    {
        // Simply get the state of the controller from XInput.
        ZeroMemory(&mControllerState, sizeof(mControllerState));
        DWORD dwResult = XInputGetState(i, &mControllerState);

        if (dwResult == ERROR_SUCCESS)
            return;
    }
}

float GetThumbstickAmount(const int rawVal)
{
    const int inputDeadzone = static_cast<int>(0.24f * float(0x7FFF)); // Default to 24% of the +/- 32767 range.
    const int deadzoneVal = abs(rawVal) < inputDeadzone ? 0 : rawVal + inputDeadzone * Sign(rawVal);
    return float(deadzoneVal) / float(0x7FFF - inputDeadzone);
}

void App::Update(bool /*mouseButtons*/[2], int /*mouseX*/, int /*mouseY*/)
{
    static const auto startTime = chrono::high_resolution_clock::now();
    auto frameTime = chrono::high_resolution_clock::now();
    auto frameMs = chrono::duration_cast<chrono::milliseconds>(frameTime - mLastFrameTime);
    //float frameS = chrono::duration_cast<chrono::milliseconds>(frameTime - startTime).count() * 1e-3f;
    mLastFrameTime = frameTime;

    UpdateControllerState();
    float xRot = GetThumbstickAmount(mControllerState.Gamepad.sThumbRX) * float(frameMs.count()) * -1e-3f;
    float yRot = GetThumbstickAmount(mControllerState.Gamepad.sThumbRY) * float(frameMs.count()) * 1e-3f;
    mScene.GetCamera().RotateCam(xRot, yRot);
    Vector4 camForward = mScene.GetCamera().GetCameraToWorld().GetRow(2);
    Vector4 camStrafe = mScene.GetCamera().GetCameraToWorld().GetRow(0);
    float forward = GetThumbstickAmount(mControllerState.Gamepad.sThumbLY) * float(frameMs.count()) * 5e-3f;
    float strafe = GetThumbstickAmount(mControllerState.Gamepad.sThumbLX) * float(frameMs.count()) * 5e-3f;
    Vector4 camTranslate = camForward * forward + camStrafe * strafe;
    mScene.GetCamera().TranslateCam(Vector3(camTranslate.x(), camTranslate.y(), camTranslate.z()));

    /*
    auto movingSpherePos = Vector3(sin(frameS), cos(frameS), cos(frameS)) * 5.0f;
    mScene.GetPrimitive(6) = Primitive(Sphere(movingSpherePos, 3.0f), Vector3(0.6f, 0.6f, 0.05f));
    */

    UpdateTexture(static_cast<unsigned>(frameTime.time_since_epoch().count()));

    mDevice.ClearDefaultRenderTarget();
    mDevice.SetDefaultRenderTarget();

    ID3D11DeviceContextPtr deviceContext;
    mDevice.GetD3D11Device()->GetImmediateContext(&deviceContext);

    deviceContext->IASetPrimitiveTopology(D3D11_PRIMITIVE_TOPOLOGY_TRIANGLELIST);
    deviceContext->IASetInputLayout(mInputLayout);
    deviceContext->IASetIndexBuffer(mQuadIndexBuffer, DXGI_FORMAT_R16_UINT, 0);
    ID3D11Buffer* vbs[] = { mQuadVertexBuffer.GetInterfacePtr() };
    UINT strides[] = { sizeof(SimpleVertex) };
    UINT offsets[] = { 0 };
    deviceContext->IASetVertexBuffers(0, ArraySize(vbs), vbs, strides, offsets);
    deviceContext->VSSetShader(mVs, nullptr, 0);
    deviceContext->PSSetShader(mPs, nullptr, 0);
    ID3D11ShaderResourceView* srvs[] = { mTexView.GetInterfacePtr() };
    deviceContext->PSSetShaderResources(0, ArraySize(srvs), srvs);
    ID3D11SamplerState* samplers[] = { mSamplerState.GetInterfacePtr() };
    deviceContext->PSSetSamplers(0, ArraySize(samplers), samplers);
    deviceContext->DrawIndexed(6, 0, 0);
    ID3D11ShaderResourceView* emptySrvs[] = { nullptr };
    deviceContext->PSSetShaderResources(0, ArraySize(emptySrvs), emptySrvs);

    mDevice.Present();

    cout << frameMs.count() << endl;
}

unique_ptr<IApp> CreateApp(void* hwnd, int width, int height) {
    return unique_ptr<IApp>(new App(hwnd, width, height));
}

```

# Answer
> 7 votes
# Befunge 93

```
>"  )__:__(  @"v
v"@'--( : )--'"<
>"   )^_^(   @"v
v"@   _[_]_   "<
>"     _     @"v
@    v_v#!-"@":<
     >$ 91+,:!v
       >,: !#v_^
^            <

```

Ouput:

```
     _
   _[_]_
   (^_^)
'--( : )--'
  (__:__)

```

Change one character for infinite snowmen:

```
>"  )__:__(  @"v
v"@'--( : )--'"<
>"   )^_^(   @"v
v"@   _[_]_   "<
>"     _     @"v
@    v_v#!-"@":<
     >$ 91+,:!v
       >,: !#v_^
v            <

```

How it works: stores the characters in the snowman on the stack. @ symbolizes a new line. Then, loops through all the characters; if it is an @, print a new line: `91+,`, otherwise, print the character. Then, it checks if the end has been reached. If it has, it exits the loop: `#v_^`.

---

# Ascii art versions

```
          >")__:__(  @"v
          v            <
          >            v
       vv"@'--( : )--'"<vv
         v              v_
        >"   )"     "^"   v
      v"@   ""("   "^""_" <
      >"   "              v
        v     "_[_]_"     <<
        >>                v
          v               <
  _       >"  ":"@  ":  ::v       _
 | |     v    ::    :"  _"<      | |
 | |=====>                 v=====| |
  =======v   "@"    +0     <=======|
         >>               v
          v               <
         %v<   o     o    <v
        %v<    0     0     &%
        %>                  v
        v    "@"     :      <
        >>                 v
         v +0+0:,+19$<_v#!-<
    _____>0+!#v_v#+0!:,<@@@@ _____
    @@@@@@@$0 <@>0+0+0+0+0+ ^@@@@@

```

Outputs the exact same thing. Can also be changed to infinite snowman:

```
          >")__:__(  @"v
          v            <
          >            v
       vv"@'--( : )--'"<vv
         v              v_
        >"   )"     "^"   v
      v"@   ""("   "^""_" <
      >"   "              v
        v     "_[_]_"     <<
        >>                v
          v               <
  _       >"  ":"@  ":  ::v       _
 | |     v    ::    :"  _"<      | |
 | |=====>                 v=====| |
  =======v   "@"    +0     <=======|
         >>               v
          v               <
         %v<   o     o    <v
        %v<    0     0     &%
        %>                  v
        v    "@"     :      <
        >>                 v
         v +0+0:,+19$<_v#!-<
    _____>0+!#v_v#+0!:,<@@@@ _____
    @@@@@@v$0 <@>0+0+0+0+0+ ^@@@@@

```

---
Tags: popularity-contest
---


title: Build an exact change calculator

text:
# Question
Title: Build an exact change calculator
When I'm at a store and I pay for something in cash, I always try to give as exact change as possible in order to minimize the number of coins I have left in my wallet afterwards.

Your task is to build a program that will automate this process for me.

Your program will accept as input:

* a line containing a single decimal number representing the price of an item.
* a line consisting of a list of pairs of numbers, each pair representing the value of a denomination of coin or bill, and then the current amount of that denomination that I have in my wallet.
* a line consisting of a list of denominations that the cashier has (you may assume they have an unlimited amount of each).

For example, the following input:

```
21.36
0.01 6 0.05 2 0.10 3 0.25 4 1.00 1 2.00 2 5.00 1 20.00 5
0.01 0.05 0.10 0.25 1.00 2.00 5.00 10.00 20.00 50.00 100.00

```

represents that I'm buying an item costing $21.36, and I have six pennies, two nickels, three dimes, four quarters, one loonie, two toonies, one five-dollar bill, and five 20-dollar bills.

Your program will then output the following:

* the change that I should give to the cashier.
* the change that the cashier will give me in return. You must optimize this as well in order to have a good solution.
* the list of coins and bills still left in my wallet.
* the total number of coins and bills left in my wallet after the transaction.

In this case, the optimal output is:

```
0.01 6 0.05 2 0.10 2 0.25 4 20.00 1

0.10 1 1.00 1 2.00 2 5.00 1 20.00 4
12

```

because I have exact change and this configuration uses the most coins to give that change. The second line is blank because no change was given in return.

Note that your program must support unconventional denominations such as `0.04` or `15.32`, if they are part of the input. You are not guaranteed that every denomination will be a multiple or factor of another, except that every denomination will be a multiple of the lowest one, so that there is always a valid solution. You may assume that I will always have enough money to pay for the item whose price is listed.

In a few days, I will be posting a suite of 1,000 test cases for this program. Your program will be scored by the sum of the total number of coins and bills left in my wallet for each test case, with shorter code being a tie-breaker.

# Answer
> 2 votes
I think I have a Python 3 solution that should work for any test case. It took me quite a few tries to get something that wouldn't explode for certain degenerate inputs. It's still pretty slow for some large inputs where you have thousands of coins in your wallet to start, but I don't think it's possible to do much better in those cases (you must search a very large set of possible combinations of payment and change).

I've made two version of my solution, one that minimizes the number of coins you end up with in your wallet at the end (as per the current scoring rule), and another that minimizes the number of coins you are given in change (which is equivalent to minimizing the number of coins in your wallet at the end plus the number of coins you paid with, which Joe Z. has been considering changing the scoring rule to). You can switch which version is run by moving the leading `#` for the comment in the `if __name__ == "__main__"` block to the previous line. Both versions are based on of the same recursive change making algorithm (in the `make_change` function), they just run it with slightly different inputs.

The code exploits the effect that Cruncher noted in the question's comments, that the best overall algorithm is to give all your money to the cashier and then get ideal change for your final balance back. What my code does is give all the money to the cashier, then charge a "cost" to the solution for each coin or bill returned to the customer. The best solution is the one with the combined cost for its bills and coins. Later I do some cleaning up, and eliminate any payments that get directly returned using the same bills or coins.

For the version optimized for the original scoring rule, the cost is 1 for every coin or bill. For the alternative scoring rule, the cost is 0 for bills and coins that were originally in the customer's wallet (and are being returned), and 1 for anything that needs to come from the cashier's drawer.

The core algorithm is a depth-first search for combinations of coins that yield exact change. Larger coins are tried first, and more of them before fewer. This means the first result we find will be the "greedy" one (though we keep searching and may find a better result later).

The interesting part of the algorithm is that it keeps track of the cost of the best result found so far, and stops searching for more results down any branch that costs more than that that result. This lets it avoid considering a lot of possible combinations that require too much from the cashier (like thousands of pennies).

I do get a different optimal result for the example case given in the question, but it is in fact better for the current scoring rule (I pay several extra small bills and get a single $50 in change). My output is:

```
0.01 6 0.05 2 0.10 2 0.25 4 1.00 1 2.00 2 5.00 1 20.00 3
50.00 1
0.10 1 20.00 2 50.00 1

```

For the alternate scoring rule I get the same result shown in the question.

I've not made much effort at minimizing the number of characters in this code, though some parts were written in terse, code-golf style before I got more distracted by performance issues and correctness. I think I've factored out the all the repeated code into separate functions, but let me know if you see any obvious improvements.

```
def make_change(value, coins, best_cost=float("inf")):
    if value == 0:
        return [], 0

    best_solution=None
    for i, (coin, count, cost) in enumerate(coins):
        max_num = min(count, value//coin, best_cost//cost if cost else float("inf"))
        for num in range(max_num, 0, -1):
            coin_value = num*coin
            coin_cost = num*cost
            if coin_cost < best_cost: # this is always true the first iteration, but may not be later
                solution, solution_cost = make_change(value-coin_value, coins[i+1:],
                                                      best_cost-coin_cost)
                if solution is not None:
                    best_solution = [(coin, num)] + solution
                    best_cost = coin_cost + solution_cost
    return best_solution, best_cost

def parse():
    value = int(input().replace(".",""))
    wallet = dict(zip(*[iter(map(int,input().replace(".","").split()))]*2))
    cashier = list(map(int,input().replace(".","").split()))
    return value,wallet,cashier

def print_output(pay, change, final_wallet):
    print(" ".join("{:.2f} {}".format(coin/100, count) for coin, count in pay if count != 0))
    print(" ".join("{:.2f} {}".format(coin/100, count) for coin, count in change if count != 0))
    print(" ".join("{:.2f} {}".format(coin/100, count) for coin, count in final_wallet if count != 0))

def solve(value, wallet, coins):
    result, cost = make_change(value, coins)
    pay=[]
    change=[]
    for coin, count in result:
        if coin in wallet:
            if wallet[coin] > count:
                pay.append((coin, wallet[coin] - count))
            elif wallet[coin] < count:
                change.append((coin, count - wallet[coin]))
            del wallet[coin]
        else:
            change.append((coin, count))
    pay.extend(wallet.items())
    pay.sort()
    change.sort()
    result.sort()
    return pay, change, result

def minimize_wallet(value, wallet, cashier):
    wallet_value = sum(coin*count for coin,count in wallet.items())
    coin_dict = wallet.copy()
    coin_dict.update((coin, wallet_value//coin) for coin in cashier)
    coin_list = [(coin, count, 1) for coin, count in sorted(coin_dict.items(), reverse=True)]
    return solve(wallet_value-value, wallet, coin_list)

def minimize_change(value, wallet, cashier):
    wallet_value = sum(coin*count for coin,count in wallet.items())
    coin_list = [(coin, count, 0) for coin, count in wallet.items()]
    coin_list.extend((coin, wallet_value//coin, 1) for coin in cashier)
    coin_list.sort(key=lambda x: (-x[0], x[2]))
    return solve(wallet_value-value, wallet, coin_list)

if __name__ == "__main__":
    print_output(*minimize_wallet(*parse()))
    #print_output(*minimize_change(*parse())) # use this if the scoring rules are changed

```

I'd also like to suggest a testcase that is likely to break many implementations:

```
1.00
100.00 10000
0.01 0.05 0.10 0.25 1.00 2.00 5.00 10.00 20.00 50.00 100.00 999999.00

```

This testcase comes with a story I like to call "The bank robber and the debt limit":

> One day, Alice robbed a bank. She made a clean getaway with exactly one million dollars in $100 bills. On her way home from the bank, she stopped off at a convenience store to buy a candy bar, but realized that she had not brought her wallet with her, so the only money she had was her bag of stolen money (ten thousand $100 bills will fit snugly in a decent sized backpack if they're shrink wrapped). She hoped the clerk would be willing to break a $100 bill.
>
> Unbeknownst to Alice, Bob the convenience store clerk had been recently laid off as a worker at the US Mint. He had worked for several months this past spring and summer preparing high-denomination platinum coins in case they would be the only way for the US Government to make its interest payments without Congress increasing the debt limit. It turned out the coins were not needed, so their existence was never acknowledged. When he was told his job was being cut, Bob decided he would keep on of the coins he had worked so hard on. He smuggled out a single $1,000,000-denominated coin in his box of personal effects.
>
> Sadly for everyone involved, Bob was showing off his million dollar coin to a coworker when Alice came to his register to see if he'd give her $99 in change for her $1 candy bar. Alas, seeing the coin, Alice's compulsion to receive the smallest amount of change possible got the better of her. She misinterpreted the text on the coin saying it was "0.999999 pure Platinum" to mean it was worth that fraction of its face value. If that was the case, it would be exact change for her candy bar if she paid Bob with her backpack full of money. She'd go from having 10,000 bills to having just one coin!

Can your code satisfy Alice? Expected output:

```
100.00 10000
999999.00 1
999999.00 1

```

---
Tags: code-challenge
---