# Question
Title: Automatic price-identification of scrolls in Nethack
> OH GODS NO!! You can't leave us here with Doorknob! It'll be nethack everywhere! - 1d ago by Geobits

Well, couldn't disappoint...

## Introduction

*(you can skip this section if you don't care about exposition and/or if you have Tab Explosion Syndrome)*

One of the characteristic mechanics of Nethack (and Rogue, and similar games in the same roguelike genre) is its identification system. At the beginning of the game, only items in your starting inventory are "formally identified." The vast majority of other objects start out unknown; for example, a "shield of reflection" will initially display as a "polished silver shield" before it's identified.

A "polished silver shield" can only be a shield of reflection, but this has interesting consequences in two other cases.

1. Some items are different from each other, but have the same "appearance." For example, if you find a "gray stone," it could be one of four things: A flint stone (useless), a touchstone (can be useful), a loadstone (which will severely encumber you because it weighs a ton and you can't drop it), or a luckstone (extremely helpful, almost necessary for winning the game).
2. Many items (scrolls, wands, rings, spellbooks, some armor, etc.) have a randomized appearance. What this means is that there is a set list of possible apperances, say, potions could have; for example, \[*golden potion*, *swirly potion*, *fizzy potion*, *purple-red potion*, etc.\]. These appearances are then randomly assigned to what they actually are (*potion of healing*, *potion of paralysis*, *potion of see invisible*, *potion of polymorph*, etc.).

Which means that a *hexagonal amulet* could save your life in one game (amulet of life saving), and choke you to death the next (amulet of strangulation).

Naturally, this makes identifying items a critical part of the game. Items can be "formally identified," meaning that they will unambiguously show up as definitely being a certain item (ex. all the *jeweled wands* you find will show up as *wands of create monster*); this is done primarily via scrolls or spellbooks of identify. Typically those are in short supply, though, which brings us to...

Informal identification. This means that you're *pretty sure* (or certain) that a certain unidentified item is of a certain type (or that it can only be one of several types), but you haven't "formally" identified it yet. This can be done via several methods: engrave-testing for wands, sink-testing for rings, or, the most common method...

... price identification! Which is what this challenge is about.

In a nutshell, there are shops located throughout the Dungeons of Doom (yes, the shopkeepers thought it'd be a good idea to set up shop in some underground dungeon; don't ask why). In these shops, you can buy and sell the various items that you come across during your travels. When buying or selling an item, the shopkeeper will first tell you how much he would sell it to you / buy it from you for. Since certain items are guaranteed to have specific prices, you can use this to *informally identify* a certain type of item.

Some items, such as the *scroll of light*, are the only items to cost a certain amount, which allows you to unambiguously identify them; however, most items share a price group with other items of the same class, which only lets you narrow down the possibilities (which is still useful). However, the buy/sell prices of an item are affected by a number of variables (such as your Charisma stat). Hence the chart above.

Could you tell I like Nethack?

## Input

Input will be provided as a (vanilla, 3.4.3) Nethack game currently being played:

```
"For you, most gracious sir; only 177 for this scroll labeled VERR YED HORRE."
--More--

        ------------
        |          .                                        ---------
        |          |                         ----------     |    ^  |
        |          .##       ################.        +#   #.       .#
        |          | #                       |       _|#   #---------#
        |          | ###                   ##.<       |#   ####      #
        |          .#########################----------#      #      #
        ------------   ###     #         ############# #      #      #
           #             #  -----------  #             #      #   ####
         ###             ###|         |###             #      #   #----------
         #                 #.         |#             ### #    #   #|.???????|
        ##                  |         |#             #--------#   #|.??@????|
    ----.----###############.         |#             #|      |#   #-@???????|
    |.......+#              |         |#             #.      |#    ----------
    |.......|               |         .#              |      |#
    |......>|               -----------               |      +#
    ---------                                         --------

Wizard the Evoker         St:12 Dx:14 Co:11 In:16 Wi:12 Ch:10  Chaotic
Dlvl:2  $:0  HP:11(11) Pw:0(8) AC:9  Exp:1 T:11

```

This means that it is guaranteed to have several properties:

* It will **always** be 24 lines long.
* Each line will **always** be 80 characters or less in length.
* The second-to-last line will consist of the following "*tokens*": the player's name and title (in the form of "*foo* the *bar*"), the list of attributes (separated by a single space), and the player's alignment (Lawful, Neutral, or Chaotic). Each *token* will be separated by a variable number of spaces.1
* The list of attributes will always be `St:* Dx:* Co:* In:* Wi:* Ch:*`, where a `*` character represents an integer from 3 to 25.2 (The point of interest here is the last stat, Charisma, which you need to calculate prices.)
* The first line will always consist of a shop-related message (specifically, the message that is displayed when you are buying or selling an item). Furthermore, this item is guaranteed to be a single, unidentified, unnamed scroll. For buying an item, this is:

```
"For you, {TITLE}; only {PRICE} for this scroll labeled {LABEL}."--More--

```

and for selling, it is:

```
{SHK} offers {PRICE} gold pieces for your scroll labeled {LABEL}.  Sell it? [ynaq] (y)

```

where the "variables" listed in `{curly braces}` are the following:

+ `{TITLE}` is always one of "*good*", "*honored*", "*most gracious*", or "*esteemed*", concatenated with either "*lady*" or "*sir*".
    + `{PRICE}` is always an integer.
    + `{LABEL}` will always be one of the following (source):

    ```
    ZELGO MER       JUYED AWK YACC  NR 9             XIXAXA XOXAXA XUXAXA
    PRATYAVAYAH     DAIYEN FOOELS   LEP GEX VEN ZEA  PRIRUTSENIE
    ELBIB YLOH      VERR YED HORRE  VENZAR BORGAVVE  THARR
    YUM YUM         KERNOD WEL      ELAM EBOW        DUAM XNAHT
    ANDOVA BEGARIN  KIRJE           VE FORBRYDERNE   HACKEM MUCHE
    VELOX NEB       FOOBIE BLETCH   TEMOV            GARVEN DEH
    READ ME

    ```
    + `{SHK}` will always be one of the following (source):

    ```
    Skibbereen      Ballingeary     Inishbofin      Annootok        Abitibi
    Kanturk         Kilgarvan       Kesh            Upernavik       Maganasipi
    Rath Luirc      Cahersiveen     Hebiwerie       Angmagssalik    Akureyri
    Ennistymon      Glenbeigh       Possogroenoe    Aklavik         Kopasker
    Lahinch         Kilmihil        Asidonhopo      Inuvik          Budereyri
    Kinnegad        Kiltamagh       Manlobbi        Tuktoyaktuk     Akranes
    Lugnaquillia    Droichead Atha  Adjama          Chicoutimi      Bordeyri
    Enniscorthy     Inniscrone      Pakka Pakka     Ouiatchouane    Holmavik
    Gweebarra       Clonegal        Kabalebo        Chibougamau     Lucrezia
    Kittamagh       Lisnaskea       Wonotobo        Matagami        Dirk
    Nenagh          Culdaff         Akalapi         Kipawa
    Sneem           Dunfanaghy      Sipaliwini      Kinojevis

    ```

This message may be split onto another line (but it will never take up more than 2 lines).3
* Aside from the first few lines, all bets are off as to what the rest of the screen looks like. Nethack uses the majority of the ASCII character set. The only thing that you can safely assume is that the input will be purely ASCII (however this probably won't matter because you can discard lines 3-22 anyway).

If the input is taken as a function argument, it will be given exactly as shown in the example above (newline separated). If you input via STDIN, it will be given as 24 consecutive lines of input (again, as shown above). You may choose whether you want the input to have a trailing newline or not. The input is guaranteed to have no trailing spaces.

## Output

Output should be provided as what I should `#name` the scroll that I just price-ID'd. The naming system I use (and that I have seen others use) is:

* If the scroll is unambiguously identified as a certain scroll (identify, light, enchant weapon), `#name` it that. This is the case for scrolls of the following *base prices* (you will see how to calculate base price below): 20 -\> identify, 50 -\> light, 60 -\> enchant weapon.
* Otherwise, take the first three letters of the scroll's appearance, or the first word if it is less than 3 characters. For example, `ZELGO MER` becomes `ZEL`, `VE FORBRYDERNE` becomes `VE`, etc. Concatenate with this (a space, and then) the base price of the scroll. For example, `ELB 300`.
* If the base price can be one of two possibilities, I usually keep trying to buy or sell the item until I get an offered price that unambiguously places it into a certain price slot. However, you can't do that in this challenge, so just separate the two possible base prices with a slash (`/`). For example, `HAC 60/80`.

Here's the formula for converting the base price of an item into the price you are offered to buy it:

* start with the base price of the item
* chance of a possible 33% "unidentified surcharge," calculated via `price += price / 3`
* another chance of a 33% "sucker markup" (this isn't random chance actually, but for the purposes of this challenge it is), calculated the same way
* a charisma modifier, which is applied as follows:

```
Ch    3-5     6-7       8-10      11-15  16-17     18        19-25
Mod   +100%   +50%      +33%      +0%    -25%      -33%      -50%
Code  p *= 2  p += p/2  p += p/3  ---    p -= p/4  p -= p/3  p /= 2

```

And here's the formula for base price -\> sell price:

* start with the base price of the item
* divide this by either 2 or 3 ("normal" or "sucker markup" respectively; again, not random, but it is for the purposes of this challenge)
* chance of a further 25% reduction4, calculated via `price -= price / 4`

The division is integer division, which means the result *at each step* is rounded down. (Source: wiki, and a bit of source code digging. Reversing these formulas is your job.)

Finally, here's a handy-dandy ASCII chart that shows the possible buy prices (grouped by Charisma stat) and sell prices of a scroll with a certain base price:

```
Base  Ch<6          6-7          8-10         11-15        16-17        18           19-25        Sell
20    40/52/68      30/39/51     26/34/45     20/26/34     15/20/26     14/18/23     10/13/17     5/6/8/10
50    100/132/176   75/99/132    66/88/117    50/66/88     38/50/66     34/44/59     25/33/44     12/16/19/25
60    120/160/212   90/120/159   80/106/141   60/80/106    45/60/80     40/54/71     30/40/53     15/20/23/30
80    160/212/282   120/159/211  106/141/188  80/106/141   60/80/106    54/71/94     40/53/70     20/26/30/40
100   200/266/354   150/199/265  133/177/236  100/133/177  75/100/133   67/89/118    50/66/88     25/33/38/50
200   400/532/708   300/399/531  266/354/472  200/266/354  150/200/266  134/178/236  100/133/177  50/66/75/100
300   600/800/1066  450/600/799  400/533/710  300/400/533  225/300/400  200/267/356  150/200/266  75/100/113/150

```

(This is identical to the chart on the wiki except that it lists all possible sell prices, while the wiki chart neglects to include two of the four possible sell prices. No, I didn't manually make that chart; generated with this Ruby script.)

## Test cases

Input:

```
"For you, honored sir; only 80 for this scroll labeled LEP GEX VEN ZEA."
--More--                   #                                          #
                      ----------------                              -----
                      |              |              ------------####+   |
      -----           |              -##############+          .#   |   |
      |   .###########|           >  |#           # |          |  ##.   |
      |   |          #------------.---#           ##.          |  # -----
      -+---          ##################             ----.-------###    #
       ####                     ###                     #       #      #
          #                     #                       #     ###      ###
          ###                 ###                       #     #          #
            #                 #                         #   ###     -----|--
       -----.---            ###                     ----+---#       |...@..|
       |       |            #                       |      |#       |???+??|
       |  <    .#          ##                     ##+      |        |+?????|
       |       |#    ------.-------                 |      |        |??]?@?|
       ---------###  |            |                 |      |        --------
            #     #  |            |                 --------
                  ###|            |                       #
                    #+            |
                     --------------

Wizard the Evoker         St:11 Dx:15 Co:9 In:20 Wi:9 Ch:11  Chaotic
Dlvl:7  $:0  HP:11(11) Pw:1(8) AC:9  Exp:1

```

Output: `LEP 60/80`

---

Input:

```
"For you, most gracious sir; only 80 for this scroll labeled DAIYEN FOOELS."
--More--                                                             #
                ------------                         -----      -------
 -----          |          |                         |   |      |     |
 |!)%|          |          |     ---------------     |   |     #-     |
 |*[@|          |          .#####|   <         |#####.   |   ###|     |
 |?(?|          ---------.--    #+             |#    |   |   #  |     |
 |[!(|                  ##       |             |#    |   +#### #.     .#
 |.@.|         ##################.             +#    ---.-     #|     |#
 ---|-                ###        ---------------#       ##     #-------#
    ##                #                    ######        #     #       #
     #              ###                         #        #     #       #
     ##             #                           #        #     #       #
  ------        #####                           #        #     #       #
  |    |       -.----                           #        #     #       #
  |    .#####  |^   |                        ####        #     #       #
  |    |    #  |    |          ----          #-----------.---- #       #------
  |    |    ###|    |          |  |          #.      >       | #       #|    |
  ------      #.    |          |  |           |              .##       #|    |
               |    |          ----           |              |         #.    |
               ------                         ----------------          ------

Wizard the Evoker         St:11 Dx:14 Co:16 In:15 Wi:10 Ch:9  Chaotic
Dlvl:6  $:0  HP:11(11) Pw:9(9) AC:9  Exp:1

```

Output: `enchant weapon`

---

Input:

```
Aklavik offers 113 gold pieces for your scroll labeled GARVEN DEH.  Sell it?
[ynaq] (y)

     -----      ------                                 ---------      -------
     |   |      |    |                         #     ##.       |      |.?)%/|
     |   |    ##.    |                       -----   # |       |      |.@!=*|
     |<  |    # |    |            #        ##.   .#####+    >  |#    #-.*?@[|
     |   .##### |    |      ------------   # | { |#    |^      |#    #|.=%)+|
     ---.-      |    |      |          .#### |   |#    ---------##   #-------
       ##       -.----     #.          |     |   |#          # ###   #
       #         ########  #|          .##   |   |#            ##    #
     ###                #  #------------ #   -----#          ####    #
     #                  #######          ##########################  #
     #                    #   #                            ###----.--#
     #                    ### #                            # #|     |#
   --.----       ########################################### #.     |#
   |     |       #----------.-#                               |     |#
   |     |       #|          |#                               -------
   |     |       #|          .#
   |     |########|          |
   -------        ------------
                   #    #
Wizard the Evoker         St:9 Dx:14 Co:11 In:19 Wi:10 Ch:12  Chaotic
Dlvl:4  $:0  HP:11(11) Pw:5(9) AC:9  Exp:1 Satiated

```

Output: `GAR 300`

---

Input:

```
"For you, good lady; only 67 for this scroll labeled VE FORBRYDERNE."--More--

                                                 -------
                                               ##|     |
  ------------                                 # |     |
  |+[!/!?%[?)|                               ### |     |          --------
  |[)(!/+]?!@|               #               #   |     |        ##+      |
  |.......@..|            --------------   ###   | <   | ##       |      |
  --------+---           #|            |   #     |     |  #       |    > |
          #            ###|            .####     --.----  ###    #-      |
          #            ###.            |           #        #  ###|      |
          #          #### ---.----------           #        ######.      |
          #          ####    ##                    #         ###  --------
          #        ####       #                    #         #
          #        ####       ########################     ###
        ###      ####                            ----+---- #
        #   #    ####                            |       .##
    ----.------####                              |  ^    |
    |         +####                              |    >  |
    |         |                                  | ^     |
    -----------                                  ---------

Wizard the Evoker         St:18 Dx:18 Co:16 In:20 Wi:20 Ch:18  Chaotic
Dlvl:4  $:150 HP:11(11) Pw:5(7) AC:9  Exp:1

```

Output: `VE 100`

---

Input:

```
Droichead Atha offers 5 gold pieces for your scroll labeled XIXAXA XOXAXA
XUXAXA.  Sell it? [ynaq] (y)
                                                ------------
                   -----                        |          .#
                   |   .### -----------        #.       {  |#
       -----       |   |  # |         |      ###|          |#
       |   .#     #.   |  # |         |      #  ---------+--#
       |   |    ###-|---    |         .##  ###          ##  #
       |   |    #   # #     |         | #  #            #   #
       |   -#####   #       |         | #### ############   #
       |>  | ##     #       ---------+-  ## -.----------    # ----------
       |   .####    ###             ## #####|          |    # |.*??/?)*|
       -----   #      #             #  #    |          |    # |@*)%!)]%|
               ###    ###         ######    |          |    # |.=)!%*!!|
                 #      #         #  #      |          |    ##+@*[%)(%?|
                 #####################      |          |      |.]?*?)%%|
                    -----+---.----##########.          |      |.%)%!!!%|
                    |            +##        ------------      ----------
                    |    <       |                  #
                    |            |
                    --------------

Wizard the Digger          St:11 Dx:9 Co:14 In:6 Wi:6 Ch:9  Lawful
Dlvl:3  $:0  HP:15(15) Pw:0(1) AC:9  Exp:1

```

Output: `identify`

*(I had to manually compile Nethack with all the other shopkeeper names removed because I couldn't find a shopkeeper who had a space in his name...)*

## Rules

---

1: this isn't necessarily always true during a Nethack game, but we assume this for the sake of simplicity.

2: again, not always true. Strength can be 18/01 through 18/\**, but you don't need to handle that.

3: more gross oversimplifications. For example, it is possible for a shopkeeper to call you "scum" or "most renowned and sacred creature," but you don't have to handle any of that.

4: which a smart player gets around by repeatedly offering to sell the item until given the higher price.

# Answer
> 10 votes
## Javascript (ES6), ~~1610~~ ~~724~~ ~~601~~ ~~612~~ ~~419~~ ~~405~~ 390 bytes

```
a=>(b=a.match(/(\d+) (g|f).+d (\w{0,3})[\s\S]+h:(\d+)/),c=+b[4],d=[20,50,60,80,100,200,300].reduce((d,e)=>(f=e/2,g=~~(e/3),(b[2]=='g'?[g-(g>>2),g,f-(f>>2),f]:[e,e+g,e+g+~~((e+g)/3)].map(h=>c<6?h*2:c<8?h+h>>1:c<11?h+~~(h/3):c<16?h:c<18?h-(h>>2):c<19?h-~~(h/3):h>>1)).includes(+b[1])?[...d,e]:d),[]),i={20:'identify',50:'light',60:'enchant weapon'}[d[0]],j=b[3]+' '+d[0],d[1]?j+'/'+d[1]:i||j)

```

~~**Large wall of text, meet large wall of code.**~~

### Ungolfed

```
inp => (
    extraction = inp.match(/(\d+) (g|f).+d (\w{0,3})[\s\S]+h:(\d+)/),

    charisma = +extraction[4],

    allowed = [20, 50, 60, 80, 100, 200, 300].reduce((allowed, base) => (
        tmp1 = base / 2,
        tmp2 = ~~(base / 3),
        (extraction[2] == 'g' ?
              [tmp2 - (tmp2 >> 2), tmp2, tmp1 - (tmp1 >> 2), tmp1]
          :
              [base, base + tmp2, base + tmp2 + ~~((base + tmp2) / 3)].map(val =>
                  charisma < 6 ?
                      val * 2
                  : charisma < 8 ?
                      val + val >> 1
                  : charisma < 11 ?
                      val + ~~(val / 3)
                  : charisma < 16 ?
                      val
                  : charisma < 18 ?
                      val - (val >> 2)
                  : charisma < 19 ?
                      val - ~~(val / 3)
                  : val >> 1
          )).includes(+extraction[1]) ? [...allowed, base] : allowed
    ), []),

    name_ = {
        20: 'identify',
        50: 'light',
        60: 'enchant weapon'
    }[allowed[0]],

    tmp3 = extraction[3] + ' ' + allowed[0],

    allowed[1] ?
        tmp3 + '/' + allowed[1]
    :
        name_ || tmp3
)

```

### Example

```
document.getElementById('input').value = `Droichead Atha offers 5 gold pieces for your scroll labeled XIXAXA XOXAXA
XUXAXA.  Sell it? [ynaq] (y)
                                            ------------
               -----                        |          .#
               |   .### -----------        #.       {  |#
   -----       |   |  # |         |      ###|          |#
   |   .#     #.   |  # |         |      #  ---------+--#
   |   |    ###-|---    |         .##  ###          ##  #
   |   |    #   # #     |         | #  #            #   #
   |   -#####   #       |         | #### ############   #
   |>  | ##     #       ---------+-  ## -.----------    # ----------
   |   .####    ###             ## #####|          |    # |.*??/?)*|
   -----   #      #             #  #    |          |    # |@*)%!)]%|
           ###    ###         ######    |          |    # |.=)!%*!!|
             #      #         #  #      |          |    ##+@*[%)(%?|
             #####################      |          |      |.]?*?)%%|
                -----+---.----##########.          |      |.%)%!!!%|
                |            +##        ------------      ----------
                |    <       |                  #
                |            |
                --------------

Wizard the Digger          St:11 Dx:9 Co:14 In:6 Wi:6 Ch:9  Lawful
Dlvl:3  $:0  HP:15(15) Pw:0(1) AC:9  Exp:1`;

func=a=>(b=a.match(/(\d+) (g|f).+d (\w{0,3})[\s\S]+h:(\d+)/),c=+b[4],d=[20,50,60,80,100,200,300].reduce((d,e)=>(f=e/2,g=~~(e/3),(b[2]=='g'?[g-(g>>2),g,f-(f>>2),f]:[e,e+g,e+g+~~((e+g)/3)].map(h=>c<6?h*2:c<8?h+h>>1:c<11?h+~~(h/3):c<16?h:c<18?h-(h>>2):c<19?h-~~(h/3):h>>1)).includes(+b[1])?[...d,e]:d),[]),i={20:'identify',50:'light',60:'enchant weapon'}[d[0]],j=b[3]+' '+d[0],d.length-1?j+'/'+d[1]:i||j);

function run() {
  try {
    document.getElementById('output').value = func(document.getElementById('input').value);
  } catch (e) {
    document.getElementById('output').value = 'ERROR!';
  }
}
```

```
<textarea id="input" placeholder="input" rows="20" cols="70"></textarea>
<br>
<button onclick="run()">Run</button>
<br>
<textarea id="output" placeholder="output" disabled="disabled"></textarea>
```

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


# Question
Title: Find the Interwoven Source Codes (Robbers)
This is the robbers' thread. For the cops' thread, go here.

# Introduction

For this Cops/Robbers challenge, the cops will write output-producing programs and interweave them together. It is the robber's job to pick apart the cops' programs to produce the desired outputs.

# Robber rules

Robbers will try to find the different programs that people post in submissions to the cops' thread (linked above). If a robber solves a cop's code, they must post the separated programs and match them with their outputs in an answer here and post that they have cracked the code on the cop's answer.

# Scoring

There are two components that are added together when scoring a cracked submission.

* 2 to the power of the number of different programs used in the cop's answer
* Round the number of bytes in the interweaving **down** to the nearest power of 2.

For example, if a robber cracks `TIliGoEnR` as being `TIGER` and `lion`, then the robber receives 2^2+8=12 points.

The winner of the robbers' challenge will be the person with the most points after a sufficient period of time for people to participate.

---

(Who wants to help with a snippet?)

# Answer
> 6 votes
# Vitsy, 12 points

```
'o'2\I/NO

```

Try it online!

```
a5F\aZ

```

Try it online!

The `NaN` in `NaNo` was a dead giveaway.

The obvious way to push `NaN` would be to divide **0** by itself, `2\I` pushes the input length (**0**) twice, `/` performs division, and `N` prints a float.

We're left with printing `o`, and `'o'` is a string literal that `O` prints.

Whatever characters were left had to belong to the other program. In fact, `a` pushes a linefeed, `5F` the factorial of **5** (**120**), `\a` turns that into 120 linefeeds, and `Z` prints the entire stack.

# Answer
> 4 votes
# BitShift, 2^2 + 64=68 points

cops thread

```
0101100110110101001001010110111011101110111011101101010

```

prints `! ?`

```
1011101110111011101110110101000000000110010101101101010

```

prints `? !`

### Code

```
0101100110110101001001010110111011101110111011101101010 # '! ?'
01011001101101010 # '! '
0101              # XOR 0 with 128
                  # Making current value 128 (1000 0000)
    10            # Bitshift 1 to left making 10000000 -> 01000000
      01          # Bitshift 1 to left making 01000000 -> 00100000
        101       # XOR 00100000 with 1 making it 00100001
           101010 # print 00100000 which is binary for !
010010101         #
010               # XOR 00100001 with 1 making it 00100000
   010101         # print 00100000 which is binary for <space>
10111011101110111011101101010  # '?'
101               # XOR 00100000 with 1
   1              # Bitshift 1 to left making 00100001 -> 01000010
                      # This gets repeated till 01000010 becomes 0111111
101010                # print 0111111 which is binary for ?

```

I will add some description later(split the code in the parts that print individual parts)

# Answer
> 4 votes
# PHP, 68 points

```
$c=tR;$h=s;$c=$h.$c._.$h.plit;echo$c($h);

```

Output: `Array`

```
echo quotemeta('^/]'.co.'[$');

```

Output: `\^/\]co\[\$`

---

I like this submission, because it relies on a few lesser know features - one might say *misfeatures* \- of PHP. PHP allows function references to be assigned to variables, so for example:

```
$f = function($a, $b) { return pow($a, $b); };
echo $f(2, 4);

```

would do exactly what you expect. As would:

```
$f = pow;
echo $f(2, 4);

```

...except it's not doing what you think. `$f = pow` does not assign a function reference to `$f` (that would make too much sense, right?), but rather the *string* `'pow'`. The implication is that any string may be used as a function call, if it represents the name of a defined function. Bad code waiting to happen. I don't even know why you'd *want* to allow this.

Another misfeature of PHP, is that function names and keywords are case-insensitive. I wish I were joking. So `echo pow(2, 4)`, `ECHO POW(2, 4)`, and `EcHo PoW(2,4)` are all functionally equivalent.

The last misfeature on showcase is that whenever an array is typed as a string, such as for printing, the result is always the amazingly helpful string `Array`. Take a moment to reflect on the fact that someone actually did this deliberately.

So in the first program, @insertusernamehere builds up the string `stR_split`, this string is used as a function reference (which, for reasons above, actually works), and the result, an array, is output.

# Answer
> 3 votes
# JavaScript, 68 points

Cops thread

### First program

Output: `ffttff`

```
(![]+[])[+[]]+(![]+[])[+[]]+(!![]+[])[+[]]+(!![]+[])[+[]]+(![]+[])[+[]]+(![]+[])[+[]]

```

### Second program

Output: `1010`

```
+!![]+[+[]]+(+!![])+(+[])

```

### Interweaving

```
+     !!    []             +                [    +[]]          +      (+     !![])                 +     (+[])
 (![]+  [])[  +[]]+(![]+[]) [+[]]+(!![]+[])[ +[]]    +(!![]+[]) [+[]]+  (![]+     [])[+[]]+(![]+[]) [+[]]

```

# Answer
> 3 votes
# Ruby, 68 points

First:

```
p %w(b n n s)*?a%?}

```

Second:

```
w,=?(.ord,40,?);"jivivi{2".bytes{|b|putc b-w}

```

It followed pretty naturally from working out the end, with `putc`.

# Answer
> 2 votes
# Java, 132 points

Cops thread

First program:

```
interface c{static void main(String[]g){System.out.println("Hell"\u002bg.length);}}

```

Second program:

```
class i{public static void main(String[]n){System.out.print("Bye!\n");}}

```

The first program outputs `Hell0` and the second program outputs `Bye!`

# Answer
> 2 votes
# Javascript, 132 points

### Program 1

```
var x;{;alert((f=>(f.reverse(f+~~f,Math.pow(2,Math.E))))(new Array(99).fill(0).map((x,i,f)=>i/3)).join("").replace(/../g,""))}

```

### Program 2

```
try{"function";Object.keys(f)}catch(e){f=s=>!s?f(1):"";alert(f(f(f(0/0) +f(7/5)))+f(f)+`${f}`.split``.map(e=>e.charCodeAt()*23))}

```

Whew. This was terrible.

After a lot of debugging I found out that after calling (parts of) the 2nd program, it wouldn't run again. This is because the global variable `f` was still assigned. Because of `f` being assigned, the try/catch didn't fail on `Object.keys(f)`. I don't know if this is a sneaky trick or unintentional but it caused me a headache.

Also, I believe the output of the first program is platform specific.
`/../g` removes all characters on my machine, because of the regex `.` which means any character. Escaping it with `/\../g` works however, I hope someone can shed more light onto this. Also, my output is prone to rounding errors, perhaps some global javascript variable can change this?

**Output**

```
32666666666666643233333333333336323166666666666668313333333333333231306666666666666830333333333333323029666666666666682933333333333332292866666666666668283333333333333228276666666666666827333333333333322726666666666666682633333333333332262566666666666668253333333333333225246666666666666824333333333333322423666666666666682333333333333332232266666666666668223333333333333222216666666666666821333333333333322120666666666666682033333333333332201966666666666668193333333333333219186666666666666818333333333333321817666666666666681733333333333332171666666666666668163333333333333216156666666666666615333333333333341514666666666666661433333333333334141366666666666666133333333333333413126666666666666612333333333333341211666666666666661133333333333334111066666666666666103333333333333410966666666666666933333333333334986666666666666683333333333333487666666666666677333333333333337666666666666667633333333333333656666666666666753333333333333354666666666666674333333333333334366666666666666533333333333333353266666666666666523333333333333352166666666666666713333333333333331066666666666666603333333333333330

```

This was tested on chrome 46 (my only browser), Windows 7.

I hope this is still a valid submission, despite the different output

# Answer
> 2 votes
# JavaScript (ES6), 68 points

### Program 1

```
alert((c=>c.replace(/[a-z]/gi,a=>String.fromCharCode(("Z">=a?90:122)>=(a=a.charCodeAt(0)+13)?a:a-26)))("fvzcyr"))

```

### Program 2

```
alert((b=>b.replace(/[a-zA-Z]/g,s=>String.fromCharCode(s.charCodeAt(0)+(s.toLowerCase()<'n'?13:-13))))("gbnfg"))

```

### Interweaved programs

```
 alaelretrt((((cb=>c=>b.replace(/.replace[a-(/[azA-Z]-z]/gi/g,a,s=>String=>String.fromCharCode(s.fromCharCode(("Z">=a.charCodeAt(0)?90:122)>=(a=a.charCodeAt(0+(s.toLowerCase())+13)?a<'n'?13:-13:a-26)))))))((""gfvbznfcyrg""))))
 al e r t  ( ( c =>c             .replace   (/[a     -z]/gi  ,a  =>String                       .fromCharCode(("Z">=a              ?90:122)>=(a=a.charCodeAt(0                 )+13)?a           :a-26)))    ( "  fv z  cyr " ))
   a l e rt ( ( b   =>b.replace(/        [a-    zA-Z]      /g  ,s        =>String.fromCharCode(s                     .charCodeAt(0)                           +(s.toLowerCase()       <'n'?13:-13        )))) ( "g  b nf   g "  ))

```

This would've been a lot harder, had the cop torn apart the keywords. ;)

# Answer
> 1 votes
# PHP, 24 points

Program 1

```
print!0;

```

Program 2

```
print!$x;

```

Program 3

```
print print'';

```

Tested with http://sandbox.onlinephpfunctions.com/.

# Answer
> 1 votes
# Python 2, 320 points

```
print "This"
print "hello"
print "well"
print "no"
print "alas"
print "but"
print "oh"
print "done"

```

---
Tags: code-golf, cops-and-robbers
---


# Question
Title: Score an asynchronous prisoner's dilemma game
In a round of the prisoner's dilemma exercise, two players each decide whether to *cooperate* or *defect* for that round. The scoring for a round is:

* Player A and Player B both cooperate: **1 point for both**
* Player A and Player B both defect: **2 points for both**
* Player A cooperates and Player B defects: **3 points** for cooperating Player A and **0 points** for defecting Player B

You don't need to worry about strategy, though: your program will merely be tabulating the score for a game. (In case you are already familiar with prisoner's dilemma, my "points" here correspond to "years in prison.")

Your challenge is to take input that represents the players' choices over several rounds and compute their respective total scores. One player submits choices in lowercase, `c` and `d` (for *cooperate* and *defect*), and the other submits choices in uppercase, `C` and `D`. These choices are supplied to your program as a string.

Normally, players in prisoner's dilemma submit their moves simultaneously and iteratively. In this challenge, however, the players may have submitted their choices for several rounds at once. If a player's move is out of sequence, the scoring program remembers it and matches it with the next available move from the opposing player.

Here's a sample input string:

```
cDCddDDCcCc

```

To show the matches that exist in this input, I'll call out the lowercase and uppercase separately, and pair them up:

```
cDCddDDCcCc
c  dd   c c => cddcc
 DC  DDC C  => DCDDCC

```

These will be paired into the rounds:

```
c vs D (3 pts for lowercase-player, 0 pts for uppercase-player)
d vs C (0 pts for lowercase-player, 3 pts for uppercase-player)
d vs D (2 pts for both)
c vs D (3 pts for lowercase-player, 0 pts for uppercase-player)
c vs C (1 pt for both)

```

Which produces the score `9` (lowercase) to `6` (uppercase), so the output should be `9,6` (or any unambiguous delimiter).

To express it in yet another way, here's each pairing pulled out on its own row:

```
cDCddDDCcCc
cD
  Cd
    dD
      D c
       C  c

```

There is one unmatched `C`, because the uppercase player submitted more moves than the lowercase player. That is acceptable, and it is totally ignored for scoring purposes.

Here are the requirements:

* You must write a program or function that accepts a string of the regular-expression form `/[cdCD]+/`, through some input mechanism (STDIN, function argument, read from file, etc.). (Your program may optionally accept input with a trailing newline.)
* Your program or function must output or return the players' scores as a string. The output format must start with the lowercase player's score, followed by the uppercase player's score, separated by any non-empty, non-numeric delimiter of your choice. (A trailing newline is optional.)
* If one player has more moves than the other, the excess moves are ignored.
* If all moves in the input are from exclusively one player (that is, no rounds have been played at all), then each player's score is `0`.
* The smallest submission in bytes wins.

## Test cases

```
Input:  cDCddDDCcCc
Output: 9,6         -- or any delimiter; I chose commas here

Input:  cccDDD
Output: 9,0

Input:  DDDDDDccc
Output: 9,0

Input:  cDcDcD
Output: 9,0

Input:  dcDDC
Output: 5,2

Input:  CcdCDDcd
Output: 6,6

Input:  Ddd
Output: 2,2

Input:  ccccccccccc
Output: 0,0

```

# Answer
> 3 votes
# Pyth, 23 bytes

```
jsMc2/L`C,@Gz-zG"cDDCdd

```

Test suite

---

## Explanation:

`@Gz`: Lowercase letters

`-zG`: Uppercase letters

`C,`: Pair, truncate the remainder.

```: Take the string representation of the list of pairs

`/L ... "cDDCdd`: For each letter in `"cDDCdd"`, count how many time it appears in the above string repr.

`c2`: Chop the resulting list in half.

`sM`: Add up each half.

`j`: Join on newlines and print.

---

\` must be used instead of s to make the case where one party never plays work.

# Answer
> 5 votes
## Haskell, ~~139~~ 134 bytes

```
g=filter
(n!m)(a,b)=(a+n,b+m)
f s=init$tail$show$foldr id(0,0)$zipWith(#)(g(>'a')s)$g(<'E')s
'c'# 'C'=1!1
'c'#_=3!0
_# 'D'=2!2
_#_=0!3

```

Usage example: `f "cDCddDDCcCc"` -\> `"9,6"`

15 bytes just to get the output format right, i.e. turning a pair of numbers `(x,y)` into a string `"x,y"`.

How it works:

```
               g(>'a')s        -- extract all lowercase letters
                     g(<'E')s  -- extract all uppercase letters
         zipWith(#)            -- combine both lists element wise with function #
                               -- # calls ! depending on the combination of c/d/C/D
                               -- ! takes 2 numbers a and b and returns a function
                               -- that takes a pair (x,y) and returns (x+a,y+b)
                               -- now we have a list of such functions
    foldr id(0,0)              -- apply those functions starting with (0,0)
init$tail$show                 -- format output

```

Edit: @Zgarb helped me saving 5 bytes. Thanks!

# Answer
> 4 votes
# LabVIEW, 77 Bytes

The code scans from tokens and uses those indicies to decide where the points go.

Counting goes like this

# Answer
> 3 votes
# Python 3, 110

Saved 5 Bytes thanks to FryAmTheEggman.
Saved 7 Bytes thanks to apsillers.
Saved 26 Bytes thanks to DSM.

```
x=[[],[]]
a=b=0
for m in input():x[m<'E']+=m
for w,p in zip(*x):d=p>'C';c=w<'d';b+=d*2+c;a+=3-d-2*c
print(b,a)

```

I think it's finally all golfed out.

It scans through each character in the input and sorts it based on being uppercase or not. It then does some fancy math that abuses Python's implicit conversion of bools to ints.

# Answer
> 2 votes
# JavaScript (ES6), ~~124~~ 118 bytes

```
s=>(A=B=i=0,U=(r=x=>s.replace(/c|d/g,x))``,r(l=>U[i]&&(U[i++]<'D'?l<'d'?++A&++B:B+=3:l<'d'?A+=3:(A+=2,B+=2))),A+','+B)

```

### Live demo

(Expanded slightly for readability.)

```
var f=function (s) {
    A=B=i=0;
    U=(r=function(x){return s.replace(/c|d/g,x)})("");
    r(l=>U[i]&&(U[i++]<'D'?l<'d'?++A&++B:B+=3:l<'d'?A+=3:(A+=2,B+=2)));
    return A+','+B;
}

var input = ["cDCddDDCcCc","cccDDD","DDDDDDccc","cDcDcD","dcDDC","CcdCDDcd","Ddd","ccccccccccc"];
var output = ["9,6","9,0","9,0","9,0","5,2","6,6","2,2","0,0"];
var passed = true;

for (var index=0;index<input.length;index++) {
    if (f(input[index]) !== output[index]) passed = false;
}

document.getElementById("result").textContent =
  passed ? "All tests passed." : "Some tests failed.";
```

```

```

Saved 6 bytes thanks to user81655.

# Answer
> 1 votes
# Par, 49 bytes

```
(lW▼·L)w▼·U))t˅y])[h7%Z2*↓″4>5*-]z2↔-″0<4*+╞)t.Σ¡

```

One byte is used per character. See here.

## Explanation

```
(              ## Construct array
 l             ## Read line
 W             ## Assign to w
 ▼·L)          ## Filter by immutable under lower-case
 w             ## Get w
 ▼·U)          ## Filter by immutable under upper-case
)              ##
t              ## Transpose and truncate
˅y])           ## If empty, empty 2-D matrix
[              ## Map
 h             ## Decimal to hex
 7%            ## Modulo 7
 Z             ## Assign to z
 2*↓″4>5*-     ## Score of lower case
 ]             ## Put in array
 z2↔-″0<4*+    ## Score of upper case
 ╞             ## Add to array
)              ##
t              ## Transpose and truncate
.Σ             ## Map - sum
¡              ## Empty array onto stack

```

Outputs in the form `9 6`.

# Answer
> 1 votes
# CJam, ~~92~~ ~~83~~ 81 bytes

This ended up longer than I thought it would...

```
0]K*X3tC30tG22tZ11t:L;0'a]q+{'D>}:B$_{B}%1#/z{,1>},{2<[:i:#K%L=]sY0e[{si}%}%:.+S*

```

Try it here.

Explanation (Dare I explain this? :O):

```
0]K*C3tX30tG22tZ11t:L;    e# Creates this array [0,30,0,11,0,0,0,0,0,0,0,0,3,0,0,0,22,0,0,0]
0'a]q+                    e# Creates an array that looks like [0, 'a', input string]
{'D>}:B$                  e# Sorts the array by if the int representation of each element is greater than the int value of the character 'D' (e.g. [0,C,D,a,c,d])
_{B}%1#/                  e# Finds the index of the first value in the array that is > 'D' and splits the array at that index.
z{,1>},{                  e# Zip the two sub arrays and filter for only sub arrays with more than one element. (e.g [[0,a],[C,c],[D,d]])
{2<[:i:#K%L=]s            e# For each sub array, take the first two elements, convert each to an it, calculate n=(x[0]^x[1]) mod 20, and get the nth element in the very first array, and convert it to a string
Y0e[                      e# Pad the string with 0 so it is length 2. (e.g. [["00"],["22"],["11"]])
{si}%}%:.+                e# get the numerical representation of each digit and dot sum all of them (e.g [[0,0],[2,2],[1,1] => [3,3])
S*                        e# Join with a space (e.g "3 3")

```

---
Tags: code-golf
---


title: Guess my password! (Code Golf)

text:
# Question
Title: Guess my password! (Code Golf)
So, like the title says, today you are going to guess my password (sort of). You need to make a big long list of every possible password I might be using on my 4 digit online vault.

**Specifications:**

* It could contain any 26 letters of the alphabet in UPPER CASE.
* It could contain any numbers 0-9.
* So, basically, each digit has 36 different possibilities.
* There are four digits.
* Repeat characters are allowed! (Hint: Sample space is 1,679,616 or 36^4)

**Program Requirements/Rules:**

* Program must output all possible answers to a text file or to the console, line by line. (One answer per line)
* You may not make use of any premade tools for this (Idk if any exist, but just in case)
* It must generate all 36^4 possible answers

Remember, this is a Code-golf. So shortest answer in bytes wins. Please use the standard title format of `##Language Name, Byte Size`. Even if there is a winner, feel free to post your answer. (It's always fun to see the different solutions in different languages).

**Edit:** *Not a duplicate of sugested, mines has different context, and different paremeters. (I require numbers, duplicate characters, and only UPPERCASE)*

# Answer
# Pyth - 8 bytes

```
^+jkUTG4

```

Try smaller password length online here.
> 4 votes

# Answer
## Haskell, 38 Bytes

```
mapM(\a->['A'..'Z']++['0'..'9'])"abcd"

```

yeah, it's not gonna beat Pyth. Oh well...
> 2 votes

# Answer
# Ruby, ~~64~~ 53 bytes

```
[*'A'..'Z',*'0'..'9'].repeated_permutation(4){|a|p a}

```

Probably golfable further, I'm not that good at Ruby.
> 1 votes

---
Tags: code-golf, kolmogorov-complexity
---


title: Guess the hidden communities

text:
# Question
Title: Guess the hidden communities
## Background

This challenge is about the stochastic block model. Basically, you are given an undirected graph, where the nodes represent people, and the edges represent social connections between them. The people are divided into two "communities", and two people are more likely to have a connection if they are in the same community. Your task is to guess these hidden communities based on the connections.

## Input

Your input is a 2D array of bits of size 100×100. It represents the adjacency matrix of an undirected graph of size 100. The graph is generated by the following random process:

* Each node is placed in community 0 with probability 0.5, otherwise it's placed in community 1. **The communities are not visible in the input.**
* For each pair of distinct nodes that are in the same community, put an edge between them with probability 0.3.
* For each pair of distinct nodes that are in different communities, put an edge between them with probability 0.1.

All random choices are independent.

## Output

Your output is a 1D array of bits of length 100. It represents your program's guess about the underlying communities. You are not required to correctly guess which nodes belong to community 0 and which to community 1 (which would be impossible), just the partition into two communities.

## Scoring

In this repository, you'll find a text file containing 30 lines. Each line represents a graph generated by the above process, and it consists of the array of the hidden communities, a semicolon, and a comma-separated list of rows of the adjacency matrix. You should read this text file, call your submission program on the adjacency matrix of each line, and compare its output to the underlying community structure.

Your submission's score on a particular graph is

```
min(sum_i(V[i] == W[i]), sum_i(V[i] == 1-W[i]))

```

where `V` is the array of hidden communities, `W` is your program's guess based on the adjacency matrix, and `i` ranges over their indices. Basically, this measures the number of mis-classified nodes, taking into account that you're not required to guess which community is which. The **lowest average score** over all 30 test cases wins, with byte count used as a tie breaker.

## Example

Consider the input matrix (6×6 for clarity)

```
011000
101100
110000
010011
000101
000110

```

It corresponds to the 6-node graph

```
a-b-d
|/ /|
c e-f

```

consisting of two triangles with one edge between them. Your program might guess that each triangle is a separate community, and output `000111`, where the first three nodes are in community 0 and the rest in community 1. The output `111000` is equivalent, since the order of the communities doesn't matter. If the true community structure was `001111`, then your score would be `1`, because one node is mis-classified.

## Additional rules

Your program should take no more than **5 seconds** on any single test case on a reasonably modern computer (I'm unable to test most answers, so I'll just trust you here).

You can write a full program or a function, and standard loopholes are disallowed. You are allowed to optimize your answer toward the parameters used here (size 100, probabilities 0.3 and 0.1), but not the actual test cases. I keep the right to generate a new set of graphs if I suspect foul play.

## Test program

Here's a Python 3 function that computes the score of a Python 3 function submission.

```
import time

def test_from_file(submission, filename):
    f = open(filename)
    num_graphs = 0
    total_score = 0
    for line in f:
        num_graphs += 1
        a, _, c = line.partition(';')
        V = [int(node) for node in a]
        E = [[int(node) for node in row] for row in c[:-1].split(',')]
        start = time.perf_counter()
        W = submission(E)
        end = time.perf_counter()
        x = sum(V[i]==W[i] for i in range(len(V)))
        score = min(x, len(V) - x)
        print("Scored {0:>2d} in {1:f} seconds".format(score, end - start))
        total_score += score
    f.close()
    return total_score / num_graphs

```

# Answer
> 3 votes
## R, 16/30 = 0.53333...

---

### Edit:

Here is a version that has been golfed down to 259 bytes. I am sure a much better bytecount is possible. This version takes advantage of the fact that `T` is a global variable in R which can be treated as having a value of 1. If `T` has been reassigned in your R environment, results may differ.

The code produces some warnings, but they can be ignored.

```
f=function(A){L=function(p){q=1-p;z=.1*p%o%q;x=z+t(z)+.3*(p%o%p+q%o%q);c(sum(log(x^A*(1-x)^(1-A))),(A/x-(1-A)/(1-x))%*%(2*p-1))};x=tanh(rnorm(100))/2+.5;for(i in x){t=.5+tanh(atanh(2*x-1)+T*2*(L(x)[2:101]>0)-T)/2;if(L(t)>L(x)){x=t;T=2*T}else{T=T/2}};round(x)}

```

If the adjacency matrix of your graph is saved as a 100x100 matrix `A` in R, then the vector of communities is `f(A)`. It will probably make less than one mistake!

---

### Explanation

It treats the problem as fitting a statistical model (it helps that it knows the values 0.3 and 0.1) and fits it using a sort of gradient ascent algorithm. The community membership vector is treated as containing values in \[0,1\], rather than just zeroes and ones. This enables the model to be fitted using a sort of gradient ascent. (Ascent and descent is actually by a fixed amount `delta` in each coordinate, to avoid various problems. If a step of gradient ascent fails, `delta` is adjusted down.) It's quite fast and does pretty well.

I used today's date as the random seed.

```
LL <- function(p, A){
# log-lieklihood of the model
  q <- 1-p
  x <- 0.1*(p %o% q) + 0.1*(q %o% p) + 0.3*(p %o% p) + 0.3*(q %o% q)
  sum(A*log(x) + (1-A)*log(1-x))
}

expit <- function(x) exp(x)/(1+exp(x))

gradLL <- function(p, A){
# (scalar multiple of) the gradient of the log-likelihood
  q <- 1-p
  x <- 0.1*(p %o% q) + 0.1*(q %o% p) + 0.3*(p %o% p) + 0.3*(q %o% q)
  drop((A/x - (1-A)/(1-x)) %*% (0.4*p - 0.2))
}

fit_model <- function(A, N=100){
# gradient ascent
  x <- rnorm(100)
  score <- LL(expit(x), A)
  delta <- 1
  for (i in 1:N){
    grad <- gradLL(expit(x), A)
    test <- x + delta*((grad > 0) - (grad < 0))

    test_score <- LL(expit(test), A)
    if (test_score > score){
      score <- test_score
      x <- test
      #print(score)
      delta <- (1/0.7)*delta
    } else {
      delta <- 0.7*delta
    }
  }
round(expit(x))
}

generate_A <- function(){
# generate a matrix for testing
  comms <- sample(0:1, 100, replace=T)
  A <- matrix(rep(0, 100^2), nc=100)
  for (i in 1:(nrow(A)-1)){
    for (j in (i+1):ncol(A)){
      prob <- ifelse(comms[i]==comms[j], 0.3, 0.1)
      if (runif(1) < prob) A[i,j] <- 1
    }
  }
  A <- (A + t(A))/2
  list(A=A, comms=comms)
}

test <- function(){
# test the fitting function once
  dat <- generate_A()
  fit <- fit_model(dat$A)
  sum(fit==dat$comms)
}

### performance ###

strings <- readLines("community-graphs.txt", 30)

total <- 0

set.seed(011215) # note that output is random!

for (i in 1:30){
  str_data <- strsplit(strings[i], ";")[[1]]
  comms <- as.numeric(strsplit(str_data[1], "")[[1]])
  A_str <- strsplit(str_data[2], ",")[[1]]
  A <- matrix(rep(0, 100^2), nc=100)
  for (r in 1:100){
    A[r,] <- as.numeric(strsplit(A_str[r], "")[[1]])
  }
  out <- fit_model(A)
  total <- total + min(sum(out==comms), sum(out!=comms))
}

total # 16

```

# Answer
> 2 votes
# JavaScript (ES6), Score 16.83

Just a quick and simple solution that doesn't get a very good score. I know this isn't but here's my (lightly golfed) solution in 134 bytes:

```
m=>(l=m.split`,`,n=l.map((_,i)=>[!i,0]),l.map((g,a)=>[...g].map((h,b)=>n[b][n[a][0]<n[a][1]==h|0]++)),n.map(g=>o+=g[0]<g[1]|0,o=""),o)

```

## Explanation

```
m=>(                                    // m = comma delimited input matrix string

  // Initialisation
  l=m.split`,`,                         // l = input matrix as array
  n=l.map((_,i)=>                       // n = array of each node with a count of their
                                        //     graphs to nodes of each community
    [!i,0]                              // initialise the first node to community 0
  ),

  // Find graphs
  l.map(                                // compute each node
    (g,a)=>                             // a = index of node A, g = graphs of node A
      [...g].map(                       // compute each of the node's graphs
        (h,b)=>                         // b = index of node B
                                        // h = 1 if node A has a graph to node B
          n[b][n[a][0]<n[a][1]==h|0]++  // increment node B's number of graphs to node A's
      )                                 //     community if they have a graph, else
  ),                                    //     assume and increment the other community

  // Output the results
  n.map(                                // iterate over the graphs
    g=>                                 // g = current node's graphs
      o+=g[0]<g[1]|0,                   // add the number of the predominant community to
                                        //     the output
      o=""                              // o = output string
  ),
  o                                     // return o
)

```

## Possible Improvements

* I could implement two passes in the "Find graphs" step, with the first pass getting the probable community of each node and reinitialising each node to that community

## Test

```
var solution = m=>(l=m.split`,`,n=l.map((_,i)=>[!i,0]),l.map((g,a)=>[...g].map((h,b)=>n[b][n[a][0]<n[a][1]==h|0]++)),n.map(g=>o+=g[0]<g[1]|0,o=""),o);

function test() {
  var lines = input.value.split("\n"),
      output = [],
      totalScore = 0;
  for(var i = 0; i < lines.length; i++) {
    var parts = lines[i].split(";"),
        correct = parts[0],
        matrix = parts[1],
        result = solution(matrix);
    var sum = 0,
        sumInverse= 0;
    for(var c = 0; c < correct.length; c++) {
      if(correct[c] == result[c]) sum++;
    }
    for(var c = 0; c < correct.length; c++) {
      if(correct[c] == 1 - result[c]) sumInverse++;
    }
    var score = Math.min(sum, sumInverse);
    totalScore += score;
    output.push("Test " + (i + 1) + ": Score = " + score + ", Result = " + result);
  }
  output.splice(0, 0, "Average Score: " + (totalScore / lines.length));
  results.innerHTML = output.join("\n");
}
```

```
Enter the correct result followed by ";" then the input matrix delimited by ",".<br />
Put each test on a separate line.<br />
<textarea id="input" rows="5" cols="60">111000;011000,101100,110000,010011,000101,000110</textarea><br />
<button onclick="test()">Go</button>
<pre id="results"></pre>
```

# Answer
> 1 votes
## Mathematica, score 31/15 = 2.066666...

```
Range[100]/.Thread[Alternatives@@@FindGraphCommunities[AdjacencyGraph[#,Method->{"Modularity","StopTest"->(Length[#2]==2&)}]]->{0,1}]&

```

Please don't make me recalculate the score.

---
Tags: code-challenge, graph-theory, probability-theory, classification
---


title: Write a ~ATH Interpreter

text:
# Question
Title: Write a ~ATH Interpreter
The popular webcomic Homestuck makes use of a programming language called `~ATH` to destroy universes. While this code golf challenge is **not** to write a program to annihilate our existence, we will be destroying some more tame (albeit less interesting) entities: *variables*

`~ATH` (pronounced "til death," notice how `~ath` is "tilde ath") works by creating a variable called `THIS`, executing a command with `EXECUTE`, and finishing the program with `THIS.DIE()`. A wiki page for the language's use in Homestuck can be found here. The goal of this challenge will be to create a `~ATH` interpreter.

For the sake of the challenge, I'm going to create some details of `~ATH` that don't really exist but make it (somewhat) useful.

* The language will only work with integers, which are declared with `import <variable name>;`. The variable will automatically be set to a value of 0. Only one variable at a time can be imported.
* A variable `x` can be copied by writing `bifurcate x[y,z];`, which will delete the variable `x` and replace it with identical variables `y` and `z`. Note that it cannot create a variable with the same name as the one deleted. Essentially, a variable is renamed, then a copy of the variable with a different name is created. This seems like a stupid feature, but stupidity is very deeply ingrained in Homestuck.
* The syntax for writing a program that executes code on `x` is `~ATH(x){EXECUTE(<code>)}`. If you want to execute code on two variables simultaneously, the code becomes nested, like this: `~ATH(x){~ATH(y){EXECUTE(<code>)}}`. All commands in `<code>` will be executed on both `x` and `y`.
* Now let's move onto commands. `+` increments relevant variable(s) by 1 and `-` decrements them by 1. And... that's it.
* The final feature of `~ATH` is that it kills whatever it works with. Variables are printed in the format `<name>=<value>` (followed by a newline) at the command `[<name>].DIE();`. Afterwards, the program prints the word `DIE <name>` and a newline a number of times equal to the absolute value of the value of the variable. When variables are killed simultaneously with `[<name1>,<name2>].DIE();` (you can have as many variables killed as you want, so long as they exist), the `DIE()` command is executed on the variables sequentially.

**Example programs**

Program 1:

```
import sollux;                  //calls variable "sollux"
import eridan;                  //calls variable "eridan"
~ATH(sollux){EXECUTE(--)}       //sets the value of "sollux" to -2
~ATH(eridan){EXECUTE(+++++)}    //sets the value of "eridan" to 5
[sollux].DIE();                 //kills "sollux", prints "DIE sollux" twice
~ATH(eridan){EXECUTE(+)}        //sets the value of "eridan" to 6
[eridan].DIE();                 //kills "eridan", prints "DIE eridan" 6 times

```

Output:

```
sollux=-2
DIE sollux
DIE sollux
eridan=6
DIE eridan
DIE eridan
DIE eridan
DIE eridan
DIE eridan
DIE eridan

```

Program 2:

```
import THIS;                    //calls variable "THIS"
~ATH(THIS){EXECUTE(++++)}       //sets the value of "THIS" to 4
bifurcate THIS[THIS1,THIS2];    //deletes "THIS", creates variables "THIS1" and "THIS2" both equal to 4
~ATH(THIS1){EXECUTE(++)}        //sets the value of "THIS1" to 6
[THIS1,THIS2].DIE();            //kills "THIS1" and "THIS2", prints "DIE THIS1" 6 times then "DIE THIS2" 4 times

import THAT;                                         //calls variable "THAT"
bifurcate THAT[THESE,THOSE];                         //deletes "THAT", creates variables "THESE" and "THOSE"
~ATH(THESE){~ATH(THOSE){EXECUTE(+++)}EXECUTE(++)}    //sets the value of "THESE" and "THOSE" to 3, then sets the value of "THESE" to 5
[THESE,THOSE].DIE();                                 //kills "THESE" and "THOSE", prints "DIE THESE" 5 times then "DIE THOSE" 3 times

```

Output:

```
THIS1=6
DIE THIS1
DIE THIS1
DIE THIS1
DIE THIS1
DIE THIS1
DIE THIS1
THIS2=4
DIE THIS2
DIE THIS2
DIE THIS2
DIE THIS2
THESE=5
DIE THESE
DIE THESE
DIE THESE
DIE THESE
DIE THESE
THOSE=3
DIE THOSE
DIE THOSE
DIE THOSE

```

---

This is code golf, so standard rules apply. Shortest code in bytes wins.

# Answer
# Python 2.7.6, ~~1244~~ ~~1308~~ ~~1265~~ ~~1253~~ ~~1073~~ ~~1072~~ ~~1071~~ ~~1065~~ ~~1064~~ 1063 bytes

Alright, I'm not breaking any records here but this is about the smallest Python will go insofar as reading input all at once from a file rather than sequentially over time. I'll try to one-up this later in a different language (and an interpreter, not just a parser). Until then, enjoy the disgustingly horrid monstrosity.

*Note*: opens a file called `t` in the working directory. To make it open a command line argument, add `import sys` to the top of the file and change `'t'` to `sys.argv[1]`

```
n=s='\n';m=',';X='[';Y=']';c=';';A='~ATH';D='import';b,g,k=[],[],[];r=range;l=len;f=open('t','r').read().split(n)
def d(j,u):
 p=[]
 for e in j:
  if e!=u:p.append(e)
 return''.join(p)
for h in r(l(f)):f[h]=f[h].split('//')[0].split()
while[]in f:f.remove([])
for h in r(l(f)):
 i=f[h]
 if i[0]==D and l(i)==2and i[1][l(i[1])-1]==c and d(i[1],c)not in b:g.append(0);b.append(d(i[1],c))
 elif i[0].startswith(A):
  i=i[0].split('){')
  for e in r(l(i)):
   if i[e].startswith(A):
    i[e]=i[e].split('(')
    if i[0][1]in b:g[b.index(i[0][1])]+=(i[1].count('+')-i[1].count('-'))
 elif i[0].startswith('bifurcate')and l(i)==2and i[1][l(i[1])-1]==c:
  i=i[1].split(X)
  if i[0] in b:
   z=d(d(i[1],c),Y).split(m)
   for e in r(l(z)):g.append(g[b.index(i[0])]);b.append(z[e])
   g.remove(g[b.index(i[0])]);b.remove(i[0])
 elif i[0].startswith(X)and i[0].endswith('.DIE();')and l(i)==1:
  z=d(i[0],X).split(Y)[0].split(m)
  for e in r(l(z)):
   k.append((z[e],g[b.index(z[e])]))
for e in r(l(k)):k0=k[e][0];k1=k[e][1];s+=k0+'='+str(k1)+n+('DIE '+k0+n)*abs(k1)
print s

```
> 3 votes

# Answer
## Python 2, ~~447~~ ~~475~~ ~~463~~ 443 bytes

```
exec("eNp1UUtrAjEQvu+vCEshiYnrxl7KbqOUVmjvCoUkxUdiG7BRkpW2iP3tTVwrReppMsx8r4l936x9A8JXoN5kmu/2WeCxK0KjrSu8mWmEs0Ad96YI27lDPu/1is7wKqcQ0kBLenM+ty0nilu4zqnPtYCSQcXL2P2LmNvl1i9mjWlBUhwKbRt14uhHjlSvjzVy1tqswO/7AjsSpKtwIpGvt2zALqyNnkf3k/FIolb2ACjlpe2jR6lk8fAUQbKNulx7YIF1IDkqwmZlGwQpxNXGW9cASyCHZKqFVVOCoJQOEhjxABKLO7N5QGmET5qOs/Qfoqq6TGUfb3ZlgKvOnOxTwJKpDq6HSLzsVfK1k7g1iB7Hd9/JWh3T9wclkYwTlY4odP0nnvk0C3RUwj95/ZUq".decode('base64').decode('zip'))

```

It turns out zipping and encoding the program base64 still saves bytes over the normal version. For comparison, here's the normal one:

```
import sys,re
d={}
s=sys.stdin.read()
s,n=re.subn(r"//.*?$",'',s,0,8)
s,n=re.subn(r"import (.*?);",r"d['\1']=0;",s,0,8)
s,n=re.subn(r"bifurcate (.*?)\[(.*?),(.*?)\];",r"d['\2']=d['\3']=d['\1'];del d['\1'];",s,0,8)
s,n=re.subn(r"([+-])",r"\g<1>1",s,0,8)
s,n=re.subn(r"EXECUTE\((.*?)\)",r"0\1",s,0,8)
s,n=re.subn(r"\[(.*?)\]\.DIE\(\);",r"for i in '\1'.split(','):print i+'='+`d[i]`+('\\n'+'DIE '+i)*abs(d[i])",s,0,8)
n=1
s=s[::-1]
while n:s,n=re.subn(r"\}([+-01]*);?([^}]*?)\{\)(.*?)\(HTA~",r";\g<2>0+\1=+]'\3'[d;\1",s,0,8)
exec(s[::-1])

```

Basically the "regexy wands of magic" solution that was desired. Reads in the entire program from stdin as a single string, replaces ~ATH expressions with Python expressions that do the described semantics, and exec()s the resulting string.

To see what it's doing, look at the python program the second provided test program gets translated to:

```
d['THIS']=0;
0+1+1+1+1;d['THIS']+=0+1+1+1+1+0;
d['THIS1']=d['THIS2']=d['THIS'];del d['THIS'];
0+1+1;d['THIS1']+=0+1+1+0;
for i in 'THIS1,THIS2'.split(','):print i+'='+`d[i]`+('\n'+'DIE '+i)*abs(d[i])

d['THAT']=0;
d['THESE']=d['THOSE']=d['THAT'];del d['THAT'];
0+1+1;d['THESE']+=0+1+1+00+1+1+1;d['THOSE']+=0+1+1+1+0;
for i in 'THESE,THOSE'.split(','):print i+'='+`d[i]`+('\n'+'DIE '+i)*abs(d[i])

```

It's a good thing that `00 == 0` :P

Obviously, a few bytes could be saved by exploiting ambiguity in the rules. For instance, it isn't said what should happen in the event someone tries to `DIE()` a variable that hasn't been `import`ed, or that has already been `bifurcate`d. My guess based on the description was that there should be an error. If no error is required, I could remove the `del` statement.

EDIT: Fixed a bug that the provided test cases didn't test for. Namely, the way it was, every `~ATH` block reset the variable to zero before incrementing it. It cost me 28 bytes to fix that. If anyone sees a better way to replace `~ATH` blocks, I'd love to know it.

EDIT 2: Saved 12 bytes by unrolling the regex loop, making them all subns and letting the compression take care of the repetition.

EDIT 3: Saved 20 more bytes by replacing the inner `for` loop with a string multiplication.
> 3 votes

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


title: Emoji Vending Machine

text:
# Question
Title: Emoji Vending Machine
**Can't see emoji? Click here.**

You will simulate a vending machine. The items are 56 different emojis, which can be represented as two surrogate UTF-8 characters, from: (U+D83C U+DF45) to (U+D83C U+DF7C). In HTML these emojis can be represented in UTF-16 form as **&#x1F345** through **&#x1F37C**. In base 10 the first UTF-8 character has value **55356**. The value of the second character ranges from **57157** to **57212**. Here is a CJam program that generates all the relevant emojis. To avoid confusion, this challenge will be scored in **characters, not bytes**. Some emojis are 2 characters, some are 3. http://www.lettercount.com will give you an accurate count for this challenge.

## Pricing

There are 8 different price categories:

* $1.00 :
* $1.50 :
* $2.00 :
* $2.50 :
* $3.00 :
* $3.50 :
* $4.00 :
* $4.50 :

## Displaying the Vending Machine

This is what the user sees when the program starts and after making a purchase. You can use regular numbers instead of emoji numbers, but emoji numbers have the benefit of being the same width as other emojis. If you use emoji numbers you can subtract **14 characters** from your score, because emoji numbers are 3 characters each.

```
  1⃣2⃣3⃣4⃣5⃣6⃣7⃣
A
B
C
D
E
F
G
H

```

If the user enters `G5` that selects . Entering `E6` selects .

## Adding Cash

To add money, the user should input `/` and then the code for a coin or bill. The coins are (N)ickel ($0.05), (D)ime ($0.10), and (Q)uarter ($0.25). The bills are (O)ne ($1.00), (F)ive ($5.00), (T)en ($10.00). Every time the user adds a bill or coin, the program should output `Balance: [New Balance]`. Only one bill or coin can be added each time.Here is an example containing three lines of input:

```
/D
Balance: $0.10
/Q
Balance: $0.35
/F
Balance: $5.35

```

## Selecting Items

The user selects an item by entering the item code, like `B2` or `C3`. If the user has not added any money, the program should output `Item Cost: [Cost of Item]`. If the user has added money, but it is not enough to buy the item, the output should be `Insufficient Funds. Item Cost: [Cost of Item]`. If the user did add enough money, the program should output: `Item at [Item Location] Purchased. Remaining Balance: [Balance - Cost of Item]`. Then on its own line, print out the emoji of the purchased item. Then print out the entire vending machine (See "Displaying the Vending Machine") with the purchased item replaced with (U+D83D U+DEAB) Base 10: (55357 57003).

## Ending the Program

If the user buys an item which brings his/her balance down to $0.00, the program should automatically terminate. Alternatively, if the user enters "Done" at any time, the program must give the user his/her remaining balance in change. Change must be in only Nickels, Dimes, and Quarters, and must be the smallest amount of coins possible. For example if the remaining balance is $1.45, the output should be `QQQQQDD`.

## Sample Run

(Input starts with "-")

```
  1⃣2⃣3⃣4⃣5⃣6⃣7⃣
A
B
C
D
E
F
G
H
-E1
Item Cost: $3.00
-/F
Balance: $5.00
-E1
Item at E1 Purchased. Remaining Balance: $2.00

  1⃣2⃣3⃣4⃣5⃣6⃣7⃣
A
B
C
D
E
F
G
H
-Done
QQQQQQQQ

```

## Invalid Codes

* If the input starts with `/` but is not a valid money input, output `Money not Accepted`.
* If the input is an item that has already been purchased, output `Item out of stock`
* If the input is a digit-letter combination that is not in range (like `A0` or `J2`, output "Invalid code"
* For all other invalid input, output "Error"

## Bonus (-15%) : Jam

When vending an item, there is a 10% chance the machine will jam, and the item gets stuck. Output `JAM!!!` one time. In this case the user must input "punch" or "kick". Each time the user does so, there is a 20% chance that the item will break free, and vend as normal. Until the jam clears, the only inputs recognized are "punch" and "kick". All other inputs do nothing. Here is a sample:

```
-A4
Item at A4 purchased. Remaining Balance: $1.00
JAM!!!
-punch
-kick
-kick
-punch
-punch

```

(The jam has been cleared. Resume as normal.)

## Bonus (-10%) : ID

If the user tries to buy an alcoholic beverage (any item on the last row except the baby bottle), you must demand proof of age. To do so, you ask the user to multiply two random numbers between 13 and 19 (inclusive). Output `ID required: [13-19]x[13-19] = ?`. If the user answers correctly, the purchase can go through. If not, print (U+D83D U+DD1E) base 10: (55357 56606)

## Alternative Challenge : Minecraft

This challenge seems like something possible in Minecraft. To successfully create a Minecraft version of this program, the player must

* Have an 8x7 grid to select from 56 unique items
* Be able to add money to the balance (Maybe use different types of stones for the different denominations described above.)
* Give the user the item he/she selects if they have put in enough "money"
* Return the user the appropriate amount of change at the end.

## Compatibility Mode

* ### I can only take input at the beginning of the program

+ Not to worry, you can make a program that takes all input up front. If your program has not terminated after evaluating all input, assume that "Done" is called at the end. If you do this method, you will not be eligible for any bonuses.
* ### I can't view/output emojis

+ You can copy and paste your input and output into this Stack Snippet (or here). It can understand both unicode emojis and HTML codes for emojis. If your output looks correct on this page, your program passes. Try pasting in some of the sample input/output to see how it looks.

```
function parse() {
var o = document.getElementById("output");
var text = document.getElementById("in").value;
o.innerHTML = text.replace(/\n/g,"<br/>").replace(/ /g,"&nbsp");
twemoji.parse(o);
}
```

```
<head>
<script src="//twemoji.maxcdn.com/twemoji.min.js"></script>
</head>
<body>
<h1>Emoji to Image</h1>
<textarea id="in" rows="10" cols="50"></textarea>
<input type="submit" onclick="parse()">
<div id="output"></div>
</body>
```

Here is an abbreviated compatibility-mode version of the vending machine display that you can test in the Stack Snippet:

```
   &#x31&#x20E3&#x32&#x20E3&#x33&#x20E3&#x34&#x20E3&#x35&#x20E3...
A&#x1F345&#x1F346&#x1F347&#x1F348&#x1F349...
B
...

```
* ### I can output emojis, but not to STDOUT.

+ Seemingly, the Mac OS X Terminal is the only one known to be able to output emojis. If you are not able to output emojis in your terminal, your other options are
        - Send all output to a file.
        - Display all output in a window.
        - Use the technique described in "I can't view/output emojis".

# Answer
> 9 votes
# PHP, (1295 - 14) - 25% = 960.75 characters

## Old scores ~~1315~~ ~~1351~~ ~~1361~~ ~~1295~~ ~~989~~ ~~977~~

That was fun, and it's the first answer – yeah.

```
$i=[A=>[,,,,,,],B=>[,,,,,,],C=>[,,,,,,],D=>[,,,,,,],E=>[,,,,,,],F=>[,,,,,,],G=>[,,,,,,],H=>[,,,,,,]];$p=[A=>1,B=>1.5,C=>2,D=>2.5,E=>3,F=>3.5,G=>4,H=>4.5];$v=[N=>.05,D=>0.1,Q=>.25,O=>1,F=>5,T=>10];a:$m='';$w=$x=0;$q=$c[0];$r=$c[1];$f=fgets;$n=rand;$u=number_format;if('Done'==$c&&$e=1)foreach([Q,D,N]as$_)while($b&&round($b-$v[$_],2)>=0&&$m.=$_)$b-=$v[$_];elseif('/'==$q){$v[$r]?$b+=$v[$r]:$m="Money not accepted
";$m.="Balance: $".$u($b,2);}elseif(in_array($q,range(A,Z))){if(0<$r&&8>$r--&&($_=$p[$q])){$b&&$b<$_?$m="Insufficient funds. ":0;if($b<$_)$m.="Item cost: $".$u($_,2);elseif(==$i[$q][$r])$m="Item out of stock.";else{$t=0;if(H==$q&&$r<6){$t=$n(13,19);$s=$n(13,19);echo"ID required: {$t}x$s = ?
";if($f(STDIN)!=$t*$s)$m=;else$t=0;}if(!$t){$b-=$_;if(1>$n(0,9)){$w=1;}$x=$i[$q][$r];$m="Item at $c purchased. Remaining balance: $".$u($b,2).($w?"":"
$x");$i[$q][$r]=;if(!$b)$e=1;}}}else$m="Invalid code";}if($c&&!$m&&!$e)$m=Error;system(clear);echo"  1⃣ 2⃣ 3⃣ 4⃣ 5⃣ 6⃣ 7⃣";foreach($i as$k=>$_){echo"
$k ";foreach($_ as$_)echo"$_ ";}echo"
$m
";if($w){echo"JAM!!!
";for(;$c!=kick&&$c!=punch||7>$n(0,9);$c=trim($f(STDIN)));echo"$x
";}$e?exit:$c=trim($f(STDIN));goto a;

```

As vending machines remind me of the 90s I used `goto` and for purchased items the *Space Invader*  is shown. The machine is redrawn after every command.

**Ungolfed (somehow)**

```
$i=[A=>[,,,,,,],B=>[,,,,,,],C=>[,,,,,,],D=>[,,,,,,],E=>[,,,,,,],F=>[,,,,,,],G=>[,,,,,,],H=>[,,,,,,]];
$p=[A=>1,B=>1.5,C=>2,D=>2.5,E=>3,F=>3.5,G=>4,H=>4.5];
$v=[N=>.05,D=>0.1,Q=>.25,O=>1,F=>5,T=>10];

a:
$m='';
$w=$x=0;
$q=$c[0];
$r=$c[1];
$f=fgets;
$n=rand;
$u=number_format;

if('Done'==$c&&$e=1)
    foreach([Q,D,N]as$_)
        while($b&&round($b-$v[$_],2)>=0&&$m.=$_)
            $b-=$v[$_];
elseif('/'==$q){
    $v[$r]?$b+=$v[$r]:$m="Money not accepted
";
    $m.="Balance: $".$u($b,2);
}elseif(in_array($q,range(A,Z))){
    if(0<$r&&8>$r--&&($_=$p[$q])){
        $b&&$b<$_?$m="Insufficient funds. ":0;
        if($b<$_)$m.="Item cost: $".$u($_,2);
            elseif(==$i[$q][$r])
                $m="Item out of stock.";
            else{
                $t=0;
                if(H==$q&&$r<6){
                    $t=$n(13,19);
                    $s=$n(13,19);
                    echo"ID required: {$t}x$s = ?
";
                    if($f(STDIN)!=$t*$s)
                        $m=;
                    else
                        $t=0;
                }
                if(!$t){
                    $b-=$_;
                    if(1>$n(0,9)){
                        $w=1;
                    }
                    $x=$i[$q][$r];
                    $m="Item at $c purchased. Remaining balance: $".$u($b,2).($w?"":"
$x");
                    $i[$q][$r]=;
                    if(!$b)$e=1;
                }
            }
    }else
        $m="Invalid code";
}

if($c&&!$m&&!$e)$m=Error;

system(clear);
echo"  1⃣ 2⃣ 3⃣ 4⃣ 5⃣ 6⃣ 7⃣";
foreach($i as$k=>$_){
    echo"
$k ";
    foreach($_ as$_)
        echo"$_ ";
}
echo"
$m
";

if($w){
    echo"JAM!!!
";
    for(;$c!=kick&&$c!=punch||7>$n(0,9);$c=trim($f(STDIN)));
    echo"$x
";
}

$e?exit:$c=trim($f(STDIN));
goto a;

```

<sub> Tested on OS X with PHP 5.5 and 5.6 </sub>

---

**Edits**

* *Added* **12 bytes**. Fixed exit on `Done` and golfed some strings.
* *Added* **306 bytes**. Fixed one or two bugs and added support for the bonuses. With the bonuses it's now nearly **15 bytes** shorter.
* *Added* **66 bytes**. Had to format the money differently, also had to accept more values (`[A-Z][0-9]`) for `Invalid code`.
* *Saved* **10 bytes**. Found one whitespace and turned some `.=` into `=` were applicable.
* *Saved* **36 bytes** due to some refactoring.
* *Saved* **20 bytes** by refactoring some loops and assignments.

# Answer
> 6 votes
# C# 6 (.Net Framework 4.6), ~~1356~~ ~~1324~~ ~~1304~~ ~~1311~~ ~~1307~~ ~~1238~~ ~~1235~~ ~~1231~~ 1220 Letters - 14 Letters (Emoji Numbers) - (15% Jam Bonus + 10% ID Bonus) = ~~1017~~ ~~993~~ ~~978~~ ~~972.75~~ ~~969.75~~ ~~918~~ ~~915.75~~ 904.5 Letters

```
using h=System.Console;class c{static void Main(){double b=0,z,p,x=0,i=57157,j,n,r,c,m;var a=1==0;var d=new System.Collections.Hashtable();for(;i<57213;)d.Add(x++,""+(char)55356+(char)i++);for(var e=new System.Random();;){for(w("  1⃣ 2⃣ 3⃣ 4⃣ 5⃣ 6⃣ 7⃣"),x=0;x<8;x++,w(""))for(h.Write((char)('A'+x)),i=0;i<7;)h.Write(" "+d[x*7+i++]);for(;;){var k=h.ReadLine();if(k[0]==47){var l=k[1];z=b;b+=l=='N'?.05:l=='D'?.1:l=='Q'?.25:l=='O'?1:l=='F'?5:l=='T'?10:0;a=a|z!=b;w(z!=b?$"Balance {b:0.00}":"Money not Accepted");}else{if(k=="Done"){for(;b/.25>=1;b-=.25)h.Write("Q");for(;b/.1>=1;b-=.1)h.Write("D");for(;b/.05>=1;b-=.05)h.Write("N");return;}r=k[0]-65;c=k[1]-49;if(r<0|r>7|c<0|c>6)w("Invalid code");else{p=1+r/2;if(!a|p>b)w($"{(a&p>b?"Insufficient Funds. ":"")}Item Cost: ${p:0.00}");else{m=r*7+c;if(d[m]=="")w("Item out of stock");else{if(r>6&c<6){j=e.Next(13,20);n=e.Next(13,20);w($"ID required: {j}x{n} = ?");if(int.Parse(h.ReadLine())!=j*n){w("");break;}}b-=p;w($"Item at {k} Purchased. Remaining Balance: ${b:0.00}");if(e.Next(10)==1)for(w("Jam!!!");;){var f=h.ReadLine();if((f=="punch"|f=="kick")&e.Next(10)<2)break;}w(""+d[m]);d[m]="";if(b==0)return;break;}}}}}}}static void w(string s)=>h.WriteLine(s);}

```

slightly more ungolfed for use in LinqPad 5 (C# 6). Use h=System.Console in F4.

```
void Main()
{
    double b=0,z,p,x=0,i=57157,j,n,r,c,m;
    var a = 1==0;
    var d = new Hashtable();
    for (; i < 57213;) d.Add(x++, ""+(char)55356 + (char)i++);
    for (var e = new Random(); ;)
    {
        for (w("  1⃣ 2⃣ 3⃣ 4⃣ 5⃣ 6⃣ 7⃣"), x = 0; x < 8; x++, w(""))
            for (h.Write((char)('A' + x)), i = 0; i < 7;)
                h.Write(" " + d[x * 7 + i++]);

        for (; ;)
        {
            var k = h.ReadLine();
            if (k[0] == 47)
            {
                var l = k[1];
                z = b;
                b += l == 'N' ? .05 : l == 'D' ? .1 : l == 'Q' ? .25 : l == 'O' ? 1 : l == 'F' ? 5 : l == 'T' ? 10 : 0;
                a = a|z!=b;
                w(z != b ? $"Balance {b:0.00}" : "Money not Accepted");
            }
            else
            {
                if (k == "Done")
                {
                    for (; b / .25 >= 1; b -= .25) h.Write("Q");
                    for (; b / .1 >= 1; b -= .1) h.Write("D");
                    for (; b / .05 >= 1; b -= .05) h.Write("N");
                    return;
                }
                r = k[0] - 65;
                c = k[1] - 49;
                if(r<0|r>7|c<0|c>6)w("Invalid code");
                else
                {
                    p = 1 + r / 2;
                    if (!a | p > b) w($"{(a&p>b?"Insufficient Funds. ":"")}Item Cost: ${p:0.00}");
                    else
                    {
                        m = r * 7 + c;
                        if (d[m] == "")
                            w("Item out of stock");
                        else
                        {
                            if (r > 6 & c < 6)
                            {
                                j = e.Next(13, 20);
                                n = e.Next(13, 20);
                                w($"ID required: {j}x{n} = ?");
                                if (int.Parse(h.ReadLine()) != j * n)
                                {
                                    w("");
                                    break;
                                }
                            }

                            b -= p;
                            w($"Item at {k} Purchased. Remaining Balance: ${b:0.00}");
                            if (e.Next(10) == 1)
                                for (w("Jam!!!"); ;)
                                {
                                    var f = h.ReadLine();
                                    if ((f == "punch" | f == "kick") & e.Next(10) < 2)
                                        break;
                                }
                            w(""+d[m]);
                            d[m] = "";
                            if (b == 0) return;
                            break;
                        }
                    }
                }
            }
        }
    }
}

void w(string s)=>h.WriteLine(s);

```

edit: thanks for the for(;;) hint ;)

edit: Strike !! Better than PHP ;-)

edit: Removed 24 Letters. Still something left for php.

edit: Removed 20 Letters by switching from decimal to double.

edit: Removed 7 Letters by switching to Emoji Numbers

edit: Removed 4 Letters by switching everything to double instead of a mix of double and ints.

edit: Removed 69 Letters - found dead code o\_O Best Entry C# :D

edit: Removed 3 Letters - switched last if-else statement

edit: Removed 4 Letters - switched from short-circuit operators (&& and ||) to normal & and |

edit: Removed 11 Letters - switched from h.WriteLine to w() with conditional verbatim string.

---
Tags: code-golf
---


title: Force an Average on an Image

text:
# Question
Title: Force an Average on an Image
Write a program that takes in a standard truecolor image and a single 24-bit RGB color (three numbers from 0 to 255). Modify the input image (or output a new image with the same dimensions) such that its *average color* is exactly the single color that was input. You may modify the pixels in the input image in any way you like to achieve this, **but the goal is to make the color changes as visually unnoticeable as possible**.

The *average color* of an RGB image is really a set of three arithmetic means, one for each color channel. The average red value is the sum of the red values across all the pixels in the image divided by the total number of pixels (the image area), rounded down to the nearest integer. The green and blue averages are calculated in the same way.

This Python 2 (with PIL) script can compute the average color of most image file formats:

```
from PIL import Image
print 'Enter image file'
im = Image.open(raw_input()).convert('RGB')
pixels = im.load()
avg = [0, 0, 0]
for x in range(im.size[0]):
    for y in range(im.size[1]):
        for i in range(3):
            avg[i] += pixels[x, y][i]
print 'The average color is', tuple(c // (im.size[0] * im.size[1]) for c in avg)

```

(There are similar average color programs here, but they don't necessarily do the exact same calculation.)

The main requirement for your program is that for *any* input image, its corresponding output's average color must *exactly* match the color that was input - as judged by the Python snippet or some equivalent code. The output image must also have the exact same dimensions as the input image.

So you could technically submit a program that simply colors the entire input the specified average color (because the average would always be that color), but **this is a popularity contest \- the submission with the highest number of votes will win**, and such a trivial submission will not get you many upvotes. Novel ideas like taking advantage of quirks in human vision, or shrinking the image down and drawing a colored border around it will (hopefully) get you votes.

Note that certain combinations of average colors and images necessitate extremely noticeable color changes. For example, if the average color to match were black (0, 0, 0), *any* input image would need to be made completely black because if any pixels had non-zero values, they would make the average non-zero as well (barring round-off errors). Keep such limitations in mind when voting.

## Test Images

Some images and their default average colors to play around with. Click for full sizes.

**A.** average (127, 127, 127)

From fejesjoco's *Images with all colors* answer. Found original on his blog.

**B.** average (62, 71, 73)

Yokohama. Provided by Geobits.

**C.** average (115, 112, 111)

Tokyo. Provided by Geobits.

**D.** average (154, 151, 154)

Escher's *Waterfall*. Original.

**E.** average (105, 103, 102)

Mount Shasta. Provided by me.

**F.** average (75, 91, 110)

*The Starry Night*

## Notes

* The exact input and output formats and image file types your program uses does not matter much. Just make sure it is clear how to use your program.
* It is probably a good idea (but not technically a requirement) that if an image already has the goal average color, it should be output as is.
* Please post test images with the average color input as either (150, 100, 100) or (75, 91, 110), so voters can see the same inputs across different solutions. (Posting more examples than this is fine, even encouraged.)

# Answer
> 12 votes
# Python 2 + PIL, simple colour scaling

```
from PIL import Image
import math

INFILE = "street.jpg"
OUTFILE = "output.png"
AVERAGE = (150, 100, 100)

im = Image.open(INFILE)
im = im.convert("RGB")
width, height = prev_size = im.size
pixels = {(x, y): list(im.getpixel((x, y)))
          for x in range(width) for y in range(height)}

def get_avg():
    total_rgb = [0, 0, 0]

    for x in range(width):
        for y in range(height):
            for i in range(3):
                total_rgb[i] += int(pixels[x, y][i])

    return [float(x)/(width*height) for x in total_rgb]

curr_avg = get_avg()

while tuple(int(x) for x in curr_avg) != AVERAGE:
    print curr_avg
    non_capped = [0, 0, 0]
    total_rgb = [0, 0, 0]

    for x in range(width):
        for y in range(height):
            for i in range(3):
                if curr_avg[i] < AVERAGE[i] and pixels[x, y][i] < 255:
                    non_capped[i] += 1
                    total_rgb[i] += int(pixels[x, y][i])

                elif curr_avg[i] > AVERAGE[i] and pixels[x, y][i] > 0:
                    non_capped[i] += 1
                    total_rgb[i] += int(pixels[x, y][i])

    ratios = [1 if z == 0 else
              x/(y/float(z))
              for x,y,z in zip(AVERAGE, total_rgb, non_capped)]

    for x in range(width):
        for y in range(height):
            col = []

            for i in range(3):
                new_col = (pixels[x, y][i] + 0.01) * ratios[i]
                col.append(min(255, max(0, new_col)))

            pixels[x, y] = tuple(col)

    curr_avg = get_avg()

print curr_avg

for pixel in pixels:
    im.putpixel(pixel, tuple(int(x) for x in pixels[pixel]))

im.save(OUTFILE)

```

Here's a naïve approach which should serve as a good baseline. At each iteration, we compare our current average with the desired average, and scale the RGB of each pixel by the according ratio. We have to be a bit careful though, for two reasons:

* Scaling 0 still results in 0, so before we scale we add something small (here `0.01`)
* RGB values are between 0 and 255, so we need to adjust the ratio accordingly to make up for the fact that scaling capped pixels doesn't do anything.

The images save as PNG because saving as JPG seems to mess up the colour averages.

# Sample output

## (40, 40, 40)

## (150, 100, 100)

## (75, 91, 110), Starry Night palette

# Answer
> 6 votes
# C++, gamma correction

This does a brightness adjustment of the image using a simple gamma correction, with the gamma value determined separately for each component to match the target average.

The high level steps are:

1. Read image and extract histogram for each color component.
2. Perform a binary search of the gamma value for each component. A binary search is performed on the gamma values, until the resulting histogram has the desired average.
3. Read the image a second time, and apply the gamma correction.

All image input/output uses PPM files in ASCII. Images were converted from/to PNG using GIMP. The code was run on a Mac, image conversions were done on Windows.

### Code:

```
#include <cmath>
#include <string>
#include <vector>
#include <sstream>
#include <fstream>
#include <iostream>

static inline int mapVal(int val, float gamma)
{
    float relVal = (val + 1.0f) / 257.0f;
    float newRelVal = powf(relVal, gamma);

    int newVal = static_cast<int>(newRelVal * 257.0f - 0.5f);
    if (newVal < 0)
    {
        newVal = 0;
    }
    else if (newVal > 255)
    {
        newVal = 255;
    }

    return newVal;
}

struct Histogram
{
    Histogram();

    bool read(const std::string fileName);
    int getAvg(int colIdx) const;
    void adjust(const Histogram& origHist, int colIdx, float gamma);

    int pixCount;
    std::vector<int> freqA[3];
};

Histogram::Histogram()
  : pixCount(0)
{
    for (int iCol = 0; iCol < 3; ++iCol)
    {
        freqA[iCol].resize(256, 0);
    }
}

bool Histogram::read(const std::string fileName)
{
    for (int iCol = 0; iCol < 3; ++iCol)
    {
        freqA[iCol].assign(256, 0);
    }

    std::ifstream inStrm(fileName);

    std::string format;
    inStrm >> format;
    if (format != "P3")
    {
        std::cerr << "invalid PPM header" << std::endl;
        return false;
    }

    int w = 0, h = 0;
    inStrm >> w >> h;
    if (w <= 0 || h <= 0)
    {
        std::cerr << "invalid size" << std::endl;
        return false;
    }

    int maxVal = 0;
    inStrm >> maxVal;
    if (maxVal != 255)
    {
        std::cerr << "invalid max value (255 expected)" << std::endl;
        return false;
    }

    pixCount = w * h;

    int sumR = 0, sumG = 0, sumB = 0;
    for (int iPix = 0; iPix < pixCount; ++iPix)
    {
        int r = 0, g = 0, b = 0;
        inStrm >> r >> g >> b;
        ++freqA[0][r];
        ++freqA[1][g];
        ++freqA[2][b];
    }

    return true;
}

int Histogram::getAvg(int colIdx) const
{
    int avg = 0;
    for (int val = 0; val < 256; ++val)
    {
        avg += freqA[colIdx][val] * val;
    }

    return avg / pixCount;
}

void Histogram::adjust(const Histogram& origHist, int colIdx, float gamma)
{
    freqA[colIdx].assign(256, 0);

    for (int val = 0; val < 256; ++val)
    {
        int newVal = mapVal(val, gamma);
        freqA[colIdx][newVal] += origHist.freqA[colIdx][val];
    }
}

void mapImage(const std::string fileName, float gammaA[])
{
    std::ifstream inStrm(fileName);

    std::string format;
    inStrm >> format;

    int w = 0, h = 0;
    inStrm >> w >> h;

    int maxVal = 0;
    inStrm >> maxVal;

    std::cout << "P3" << std::endl;
    std::cout << w << " " << h << std::endl;
    std::cout << "255" << std::endl;

    int nPix = w * h;

    for (int iPix = 0; iPix < nPix; ++iPix)
    {
        int inRgb[3] = {0};
        inStrm >> inRgb[0] >> inRgb[1] >> inRgb[2];

        int outRgb[3] = {0};
        for (int iCol = 0; iCol < 3; ++iCol)
        {
            outRgb[iCol] = mapVal(inRgb[iCol], gammaA[iCol]);
        }

        std::cout << outRgb[0] << " " << outRgb[1] << " "
                  << outRgb[2] << std::endl;
    }
}

int main(int argc, char* argv[])
{
    if (argc < 5)
    {
        std::cerr << "usage: " << argv[0]
                  << " ppmFileName targetR targetG targetB"
                  << std::endl;
        return 1;
    }

    std::string inFileName = argv[1];

    int targAvg[3] = {0};
    std::istringstream strmR(argv[2]);
    strmR >> targAvg[0];
    std::istringstream strmG(argv[3]);
    strmG >> targAvg[1];
    std::istringstream strmB(argv[4]);
    strmB >> targAvg[2];

    Histogram origHist;
    if (!origHist.read(inFileName))
    {
        return 1;
    }

    Histogram newHist(origHist);
    float gammaA[3] = {0.0f};

    for (int iCol = 0; iCol < 3; ++iCol)
    {
        float minGamma = 0.0f;
        float maxGamma = 1.0f;
        for (;;)
        {
            newHist.adjust(origHist, iCol, maxGamma);
            int avg = newHist.getAvg(iCol);
            if (avg <= targAvg[iCol])
            {
                break;
            }
            maxGamma *= 2.0f;
        }

        for (;;)
        {
            float midGamma = 0.5f * (minGamma + maxGamma);

            newHist.adjust(origHist, iCol, midGamma);
            int avg = newHist.getAvg(iCol);
            if (avg < targAvg[iCol])
            {
                maxGamma = midGamma;
            }
            else if (avg > targAvg[iCol])
            {
                minGamma = midGamma;
            }
            else
            {
                gammaA[iCol] = midGamma;
                break;
            }
        }
    }

    mapImage(inFileName, gammaA);

    return 0;
}

```

The code itself is fairly straightforward. One subtle but important detail is that, while the color values are in the range \[0, 255\], I map them to the gamma curve as if the range were \[-1, 256\]. This allows the average to be forced to 0 or 255. Otherwise, 0 would always remain 0, and 255 would always remain 255, which might never allow for an average of 0/255.

To use:

1. Save the code in a file with extension `.cpp`, e.g. `force.cpp`.
2. Compile with `c++ -o force -O2 force.cpp`.
3. Run with `./force input.ppm targetR targetG target >output.ppm`.

### Sample output for 40, 40, 40

Note that the images for all the larger samples are included as JPEGs since they exceed the SE size limit as PNGs. Since JPEG is a lossy compression format, they may not exactly match the target average. I have the PNG version of all files, which matches exactly.

### Sample output for 150, 100, 100:

### Sample output for 75, 91, 110:

# Answer
> 2 votes
# Python 2 + PIL

```
from PIL import Image
import random
import math

SOURCE = 'input.png'
OUTPUT = 'output.png'
AVERAGE = [150, 100, 100]

im = Image.open(SOURCE).convert('RGB')
pixels = im.load()
w = im.size[0]
h = im.size[1]
npixels = w * h

maxdiff = 0.1

# for consistent results...
random.seed(42)
order = range(npixels)
random.shuffle(order)

def calc_sum(pixels, w, h):
    sums = [0, 0, 0]
    for x in range(w):
        for y in range(h):
            for i in range(3):
                sums[i] += pixels[x, y][i]
    return sums

def get_coordinates(index, w):
    return tuple([index % w, index // w])

desired_sums = [AVERAGE[0] * npixels, AVERAGE[1] * npixels, AVERAGE[2] * npixels]

sums = calc_sum(pixels, w, h)
for i in range(3):
    while sums[i] != desired_sums[i]:
        for j in range(npixels):
            if sums[i] == desired_sums[i]:
                break
            elif sums[i] < desired_sums[i]:
                coord = get_coordinates(order[j], w)
                pixel = list(pixels[coord])
                delta = int(maxdiff * (255 - pixel[i]))
                if delta == 0 and pixel[i] != 255:
                    delta = 1
                delta = min(delta, desired_sums[i] - sums[i])

                sums[i] += delta
                pixel[i] += delta
                pixels[coord] = tuple(pixel)
            else:
                coord = get_coordinates(order[j], w)
                pixel = list(pixels[coord])
                delta = int(maxdiff * pixel[i])
                if delta == 0 and pixel[i] != 0:
                    delta = 1
                delta = min(delta, sums[i] - desired_sums[i])

                sums[i] -= delta
                pixel[i] -= delta
                pixels[coord] = tuple(pixel)

# output image
for x in range(w):
    for y in range(h):
        im.putpixel(tuple([x, y]), pixels[tuple([x, y])])

im.save(OUTPUT)

```

This iterates through each pixel in a random order, and reduces the distance between each component of the color of the pixel and `255` or `0` (depending on whether the current average is less or greater than the desired average). The distance is reduced by a fixed multiplicative factor. This is repeated until the desired average is obtained. The reduction is always at least `1`, unless the color is `255` (or `0`), to ensure that the processing does not stall once the pixel is close to white or black.

## Sample output

### (40, 40, 40)

### (150, 100, 100)

### (75, 91, 110)

# Answer
> 1 votes
# Java

An RNG based approach. A bit slow for large input images.

```
import java.awt.Color;
import java.awt.image.BufferedImage;
import java.io.File;
import java.util.*;

import javax.imageio.ImageIO;

public class Averager {
    static Random r;
    static long sigmaR=0,sigmaG=0,sigmaB=0;
    static int w,h;
    static int rbar,gbar,bbar;
    static BufferedImage i;
    private static File file;
    static void upRed(){
        int x=r.nextInt(w);
        int y=r.nextInt(h);
        Color c=new Color(i.getRGB(x, y));
        if(c.getRed()==255)return;
        sigmaR++;
        c=new Color(c.getRed()+1,c.getGreen(),c.getBlue());
        i.setRGB(x, y,c.getRGB());
    }
    static void downRed(){
        int x=r.nextInt(w);
        int y=r.nextInt(h);
        Color c=new Color(i.getRGB(x, y));
        if(c.getRed()==0)return;
        sigmaR--;
        c=new Color(c.getRed()-1,c.getGreen(),c.getBlue());
        i.setRGB(x, y,c.getRGB());
    }
    static void upGreen(){
        int x=r.nextInt(w);
        int y=r.nextInt(h);
        Color c=new Color(i.getRGB(x, y));
        if(c.getGreen()==255)return;
        sigmaG++;
        c=new Color(c.getRed(),c.getGreen()+1,c.getBlue());
        i.setRGB(x, y,c.getRGB());
    }
    static void downGreen(){
        int x=r.nextInt(w);
        int y=r.nextInt(h);
        Color c=new Color(i.getRGB(x, y));
        if(c.getGreen()==0)return;
        sigmaG--;
        c=new Color(c.getRed(),c.getGreen()-1,c.getBlue());
        i.setRGB(x,y,c.getRGB());
    }
    static void upBlue(){
        int x=r.nextInt(w);
        int y=r.nextInt(h);
        Color c=new Color(i.getRGB(x, y));
        if(c.getBlue()==255)return;
        sigmaB++;
        c=new Color(c.getRed(),c.getGreen(),c.getBlue()+1);
        i.setRGB(x, y,c.getRGB());
    }
    static void downBlue(){
        int x=r.nextInt(w);
        int y=r.nextInt(h);
        Color c=new Color(i.getRGB(x, y));
        if(c.getBlue()==0)return;
        sigmaB--;
        c=new Color(c.getRed(),c.getGreen(),c.getBlue()-1);
        i.setRGB(x,y,c.getRGB());
    }
    public static void main(String[]a) throws Exception{
        Scanner in=new Scanner(System.in);
        i=ImageIO.read(file=new File(in.nextLine()));
        rbar=in.nextInt();
        gbar=in.nextInt();
        bbar=in.nextInt();
        w=i.getWidth();
        h=i.getHeight();
        final int npix=w*h;
        r=new Random(npix*(long)i.hashCode());
        for(int x=0;x<w;x++){
            for(int y=0;y<h;y++){
                Color c=new Color(i.getRGB(x, y));
                sigmaR+=c.getRed();
                sigmaG+=c.getGreen();
                sigmaB+=c.getBlue();
            }
        }
        while(sigmaR/npix<rbar){
            upRed();
        }
        while(sigmaR/npix>rbar){
            downRed();
        }
        while(sigmaG/npix<gbar){
            upGreen();
        }
        while(sigmaG/npix>gbar){
            downGreen();
        }
        while(sigmaB/npix<bbar){
            upBlue();
        }
        while(sigmaB/npix>bbar){
            downBlue();
        }
        String k=file.getName().split("\\.")[0];
        ImageIO.write(i,"png",new File(k="out_"+k+".png"));
    }
}

```

Tests:

(40,40,40)

(150,100,100)

(75,91,110)

---
Tags: popularity-contest, graphical-output, image-processing
---