title: What's wrong with public variables?

text:
# Question
Title: What's wrong with public variables?
# Code Bots

I hate private and protected variables. I just want to access anything and everything!

If you are like me, then this challenge is for you!

Write a bot that ~~works together in harmony with other bots~~ makes other bots do what you want. You are a programmer, and you know how things are supposed to work. Your job is to convert as many other bots to your ways as possible.

# The Code

You will have 24 lines of code to write your bot. Each turn, every bot will execute 1 line sequentially.

Each bot stores 5 variables `A` through `E`. `A` and `B` are for personal use, `C` stores the next line to execute, `D` stores the current direction, and `E` is a random number. The variables start at 0, except for `D`, which will start at a random value. All variables have only store 0-23. Numbers larger or smaller will be modulated by 24.

In this post, I will use opponent to be the adjacent bot you are facing

Each line must contain one of the following 5 commands:

1. `Flag` does nothing. Except it's how you win
2. `Move` moves your bot in the `D`th direction. If a bot already occupies the space, no move will happen
3. `Copy Var1 Var2` copies the contents of Var1 into Var2
4. `If Condition Line1 Line2` If Condition is true, executes Line1, else Line2
5. `Block Var1` blocks the next write on a variable

A variable can be used as follows:

`#Var` will use the variable as a line number. If `A` is 17, `Copy #8 #A` will copy the contents of line 8 onto line 17. `*Var` will use the variable of your opponent. `Copy 5 *C` will set the opponent's `C` variable to `5` `Var+Var` will add the two variables. `Copy D+1 D` will rotate the bot to the right

When `D` is used as a direction, `[North, East, South, West][D%4]` will be used

These modifiers can be chained: `Copy *#*C #9` will copy the next line your opponent will execute into your own code on line 9. `**D` refers to your opponent's opponent's `D` variable.

A Condition will be evaluated as follows:

1. If `Var`:
    1. If Var is `A` through `C`, it will return true if Var is nonzero, else false.
    2. If Var is `D`, it will return true if there is a bot in the `D`th direction, else false
    3. If Var is `E`, it will return true if E is odd, else false
    4. If Var is a line, it will return true if it is a Flag line
2. If `Var1=Var2`:
    1. Returns true if both are `A-E`, and equal the same number
    2. Returns true if both are lines, and the line type is equal
3. If `Var1==Var2`:
    1. Returns true if both are `A-E`, and equal the same number
    2. Returns true if both are lines, and are identical (Flags from different bots will not be equal)

50 bots of each type will be placed in a toroidal world in the following pattern:

```
B...B...B...B...
..B...B...B...B.
B...B...B...B...
..B...B...B...B.

```

After each game of 5,000 turns, the flags on each bot will be counted. You get a point if a bot has more of your flag than any other type of flag. If the case of a tie between `N` bots, no points are given.

There will be 10 games, and scores will be accumulated at the end.

# Side Notes

End of line comments are allowed, and are denoted with `//`

Attempting to do something that doesn't make sense, such as adding to a line will do nothing

Attempting to do something on a non-existent bot will do nothing

## Infinite recursion on an `If` will end with no line being executed

`If` does not change the value of `C`

A `Block` doesn't expire until somebody attempts to write to it

Multiple variables and lines can be blocked at once

`Block`ing a variable multiple times will block multiple times as long as the second block statement is on a different line of code than your first

Spaces are only allowed between arguments (and after the command)

If a bot is shorter than 24 lines, Flag will be the rest of the lines.

# Sample Program

```
Copy 2 C        //Skip to the If line
Flag            //Where I'm storing my flag
Move            //Move in the D'th direction
If D #5 #2      //If there's a bot, copy code, otherwise, move!
Copy #1 *#E     //Copy my flag onto a random spot in my bot's code
Copy 2 C        //Skip back to the If line

```

The program will be run by my Python controller here.

**The Java controller is here** It is *fast* and looks much better than the python one.

Scoreboard:

1. 6837 $Copy
2. 3355 Lockheed
3. 1695 MindControl
4. 967 Byzantine
5. 959 AttackOrElse
6. 743 Cadmyllion
7. 367 Influenza
8. 251 TheCommonCold
9. 226 Magus
10. 137 HideBlockAttack
11. 129 RowBot
12. 123 FastMoveCloneDodge
13. 112 FastForwardClone
14. 96 QuickFreeze
15. 71 RepairAndProtect
16. 96 SuperFreeze
17. 93 RovingVirus
18. 80 ForwardClone
19. 77 FreezeTag
20. 68 Palimpseste
21. 62 BlockFreezeAttack
22. 51 RushAttackDodge
23. 46 Blocker
24. 40 TurretMaker
25. 37 Copycat
26. 37 Kamikaze
27. 35 FlagInjector
28. 33 RandomCopier
29. 31 Insidious
30. 29 HappyAsAClam
31. 25 NanoVirus
32. 21 Nullifier
33. 19 Nanoviris
34. 17 BoringCopybot
35. 16 Movebot
36. 14 Flagbot
37. 13 Neutralizer
38. 12 Cancer
39. 9 DNAbot
40. 9 Parasite
41. 8 MetaInsidious
42. 8 Rebranding
43. 8 AdaptiveBot
44. 8 ReproducingBot
45. 8 KungFuBot
46. 5 QuickFreezerbot
47. 4 Attacker

# Answer
# Flagbot

```
Flag

```

Why bother doing anything when other bots are going to be nice enough to give me their code?
> 13 votes

# Answer
# Freeze Tag

```
Move
If D #3 #2
Copy 23 C
Copy 3 C
Copy #23 *#*C
Copy #21 *#*C+1
Copy #22 *#*C+2
Copy #21 *#*C+3
Copy #22 *#*C+4
Copy #21 *#*C+5
Copy #22 *#*C+6
Copy #21 *#*C+7
Copy #22 *#*C+8
Copy #21 *#*C+9
Copy #22 *#*C+10
Copy #21 *#*C+11
Copy #22 *#*C+12
Copy #21 *#*C+13
Copy #22 *#*C+14
Copy D+1 D
Copy 0 C
Flag
Flag
Copy C+23 C

```

Trap opponent in a loop, fill him with flags, move on to next opponent.
> 8 votes

# Answer
# Parasite

Why kill other bots? This bot looks through opponent's code and replaces only the flags.

```
Copy 1 A
Copy E D
Block #A
If *#A #C+3 #C
Copy A+A+A+A+A A
Copy C+19 C
Copy #C+4 *#A
Flag
Copy 1 A
Copy E D
Block #A
If *#A #C+3 #C
Copy A+A+A+A+A A
Copy C+19 C
Copy #C+4 *#A
Flag
Copy 1 A
Copy E D
Block #A
If *#A #C+3 #C
Copy A+A+A+A+A A
Copy C+19 C
Copy #C+4 *#A
Flag

```
> 8 votes

# Answer
# $Copy

This bot uses much of the same techniques as COTO's Lockheed, so I will shamelessly borrow and enhance.

This exploits a `C` vulnerability to break blocks and even reverses the neutralizer. It is also written in absolutes because of this. I think this might break if the `C` shift is reinstated, but as long as the shift is constant, it can be rewritten to combat it.

For whatever reason, the lack of loop at the end made this bot super good.

```
Block #C+A
If D #7 #13        //If [enemy] Copy 0 ELSE block
If D #8 #0         //If [enemy] Freeze 0 ELSE block
If D #9 #6         //If [enemy] FreezeCheck ELSE Inc
Move
Copy 0 C
Copy A+5 A          //Inc
Copy 23 *C          //Copy 0
Copy #10 *#*C+23    //FreezeAttack
If *#*C==#10 #11 #5 //FreezeCheck: If [frozen] GOTO Copy Attack ELSE GOTO [1]
Copy C+23 C         //FREEZE
Copy 13 C           //GOTO Copy Attack
Copy 15 C           //Loop Copy Attack
Block #C+A
Copy D+3 *D             //Copy Attack: Spin Enemy
Copy 0 *B               //Set enemy counter (a la COTO)
Copy #*B+0 *#*C+*B+1    //Copy my lines
Copy #*B+1 *#*C+*B+2    //Copy my lines
Copy #*B+2 *#*C+*B+3    //Copy my lines
Copy *B+3 *B            //Inc counter
If *B==0 #19 #12        //Loop check
Copy D+1 D              //Turn myself

```
> 8 votes

# Answer
# Lockheed

My third (and likely final) submission to this particular bot war: the Lockheed Reactor, or "Lockheed" for short.

```
Block #C+A
If D #C+7 #C+1
Block #C+A
Move
Copy A+5 A
If A==0 #C+12 #C+21
Copy C+17 C
Copy D+3 *D
Copy C+9 C
Copy C+21 C
Copy C+23 C
Copy #C+23 *#*C+2
Copy #C+22 *#*C+1
Copy 0 *A
Copy #*A+C+9 *#*C+*A+1
Copy *A+1 *A
If *A==0 #C+15 #C+17
Copy D+1 D
Copy C+5 C

```

Special thanks goes to @Wasmoo, who shared his discovery of the "'Blocking a variable multiple times will block multiple times as long as the second block statement is on a different line of code than your first.' simply isn't true" exploit. I make extensive use of it.

Also, thanks goes to Nathan Merill for administrating the competition and for publishing the simulator. The simulator is utterly invaluable in tuning bots. I wouldn't have believed it if I hadn't simulated it with my own eyes, but the addition or removal of the most conceptually minor bot feature can mean the difference between great success and abject failure. I'm torn as to whether that's a good thing or not.
> 7 votes

# Answer
# Attack Or Else

Seeing as defensive robots like Byzantine were doing so well, I decided to make a defensive robot as well.

This has two sets of patterns, depending on whether or not the enemy is present.

* If the enemy is not present, it blocks its lines for 3 turns and then moves.
* If the enemy is present, ~~it alternates between copying its flag and copying code that will cause the enemy to copy that flag (a weak replicator)~~ it copies its flag
* At the end of the loop, it changes to a random direction and continues
* Most aspects of its code is duplicated

More testing showed a few important concepts:

* "Turn random" performed dramatically better than "Turn right" (+2700 over alternative)
* Block increment of `A+7` shown to be more effective than any other increment (+200 over next best)
* "Direct attack" shown to be better than "Weak replicator" (+900 over alternative)
* Defense of "3-1-2-1" better than other combinations (+200 over next best)
* Duplicated attack, block, and loop code improves its score (+300 over non-duplicated)
* Duplicated block increment does not improve its score (+400 over duplicated)

Observing the simulation graphically via the Java UI helped a lot. Thank you! Below is the new and improved code. I don't think I can do anything more.

```
Block #C+A          //Dynamic block for If statements
If D #20 #0
If D #19 #8
If D #20 #23
If D #19 #0
If D #20 #8
If D #19 #23
Copy A+7 A          //Increment dynamic block
Block #C+A          //Dynamic block for If statements
If D #19 #8
If D #20 #0
If D #19 #8
If D #20 #23
If D #19 #8
If D #20 #0
If D #19 #23
Copy E D            //Turn Random
Copy 23 C           //Loop to beginning
Copy 23 C           //Loop to beginning
Copy #22 *#*C+1     //Copy my flag to the enemy's next
Copy #21 *#*C+1     //Copy my flag to the enemy's next
Flag
Flag
Move

```
> 6 votes

# Answer
# Super Freeze

```
Move                    // start moving!
Block #E
If D #12 #0             // 8 turns of attack or move
If D #12 #0
If D #12 #0
If D #12 #0
If D #12 #0
If D #12 #0
If D #12 #0
If D #12 #0
Copy D+1 D              // change direction
Copy 0 C                // start over
If *#*C==#23 #13 #14    // if opponent is frozen, give them a flag, otherwise freeze them
Copy #C+13 *#E          // give a flag to opponent
Copy #23 *#*C           // copy freeze line to opponent
Flag                    // 8 flags, one per If above
Flag
Flag
Flag
Flag
Flag
Flag
Flag
Copy C+23 C             // this line freezes any bot that executes it

```

This bot keeps trying to freeze the bot in front of it until it works, then writes a bunch of flags to random lines, and after 8 turns of that it rotates and moves on to another opponent.
> 5 votes

# Answer
# Row Bot

```
Move
If D #7 #0
If D #7 #0
If D #7 #0
If D #7 #0
If D #7 #0
Copy 0 C
If D=*D #9 #8     //If they point in a different direction
Copy *D D           //fix that
If #A==*#A #10 #11  //Did we copy line A already?
Copy A+1 A          //If so, A++
Copy #A *#A         //else, copy it!

```

Will move until it finds a robot.
Will set that robot in the same direction as itself.
Will then copy its code into the robot.
This should make a row of "Row Bot" Robots. :)
> 5 votes

# Answer
# Byzantine

A highly defensive bot that institutes multiple blocks on its flags and most sensitive instructions, including meta-blocks (i.e. blocks on critical block instructions).

It also moves constantly in unpredictable ways, and plants flags in numerous locations on opponents on a best-effort basis.

```
Block #A
Block #A+1
Block #A+2
Copy E D
Move
Block #A+3
Block #A+4
Move
Copy #22 *#*C+1
Copy E D
Move
Block #A+5
Block #A+6
Block #A+7
Move
Copy #22 *#23
Block #A+8
Block #A+9
Block #A+10
Copy #22 *#2
Copy A+14 A
Move
Flag
Copy #22 *#*C+12

```

Not sure how it will perform, since I can't simulate. But we'll give it a shot. ;)

---

### Disclaimer

I wrote this before being kindly informed by PhiNotPi that conditional logic is cost-free. However, I've decided to leave it in since one can never have too many bots.
> 5 votes

# Answer
# Meta Insidious

This bot freezes and then converts opponents into less efficient versions of Sparr's Insidious, which in their turn, will turn opponents into bots that spam flags for me. This is likely the most complex bot I've written and I thus expect it to do terrible, there was no space for blocking and only one flag fitted in the code. Turning a bot into an insidious clone also takes too long.

The biggest challenge was writing the code for the insidious clones in such a way that it works regardless of its position in the bot. The freeze gets removed when I paste the second to last code exactly where the freeze is located, this starts up the opponent just in time.

```
If D #2 #1
Copy 23 C
Copy #8 *#*C // freeze the opponent
Copy 9 A
Copy #A *#A+*C // copy the next line at the appropriate  line
Copy A+1 A
If A==0 #7 #23
Copy 23 C
Copy C+23 C
If D #C+2 #C+23 // the code for the Insidious clone starts here
Copy C+21 C
Copy C+2 C
If D #C+6 #C+22
If D #C+5 #C+22
If D #C+4 #C+20
If D #C+3 #C+19
If D #C+2 #C+18
Copy E D
Copy #C+7 *#*C
Flag
Copy C+3 A
Copy #C+22 #A
Copy A+1 A
Copy C+21 C // And ends here

```
> 4 votes

# Answer
# Cadmyllion

"I just entered a bot in the battle royale," I say. "It moves every few turns to prevent attacks by slower bots."

"What do you mean by slower bots?" PhiNotPi asks.

"Bots that are stuck evaluating long chains of conditional logic," I reply.

"'If' statements that redirect to other statements---including other 'if' statements---are all executed on the same turn," says PhiNotPi.

"Sweet massacred rules of assembly code!" I cry. "Who came up with that idea?"

...and thus is the story of how Cadmyllion came about.

Cadmyllion: the bot that happily exploits the surreal ability to evaluate infinitely many conditional expressions in a single instruction... by making pretty much every thing it does conditional.

### Code

```
If D #15 #19
Move
If D #16 #20
Copy D+3 D
Block #A
If D #15 #20
Copy A+1 A
If D #16 #1
Move
If D #15 #19
If D #16 #4
Copy E D
Block #A+12
Copy C+10 C
Flag
If *#0==#14 #17 #21
If *#0==#14 #18 #21
If *#*C+1==#14 #18 #22
Copy *C+11 *C
Block #A+6
Block #A+18
Copy #14 *#0
Copy #23 *#*C+1
Flag

```
> 4 votes

# Answer
# Repair and Protect

This bot repairs its own code, while protecting the newly repaired lines.

```
If #A==#A+16 #C+1 #C
Copy #A #A+8
Block #A+8
Copy A+1 A
Copy E D
Move
Copy #C+1 *#*C
Flag
If #A==#A+16 #C+1 #C
Copy #A #A+8
Block #A+8
Copy A+1 A
Copy E D
Move
Copy #C+1 *#*C
Flag
If #A==#A+16 #C+1 #C
Copy #A #A+8
Block #A+8
Copy A+1 A
Copy E D
Move
Copy #C+1 *#*C
Flag

```

Explanation:

The initial value of `A` is `0`, and the lines are numbered 0-23. If the `If` statement is executed and is false, it does attempt the execute the same line again. The controller does not allow a bot to execute the same line twice, so the turn is ended and `C` is incremented to `1`.

The next line, `Copy #A #A+8` is actually performed regardless of the value of the `If` statement. The difference is that it is executed twice if true and once if false. If the line `#A+8` is blocked (which happens eventually), then performing it twice with actually copy, while performing it once will only unblock it. Then, the newly copied line is blocked to preserve it.
> 3 votes

# Answer
# Insidious

```
Move
If D #4 #0
If D #4 #0
Copy 0 C
Copy 4 C
If D #12 #11
If D #12 #11
If D #12 #11
If D #12 #11
If D #12 #11
Copy D+1 D
If D #4 #3
Copy #C+8 *#*C
Flag
Copy C A
Copy #C+22 #A
Copy A+23 A
Copy C+21 C

```

Inspired by @Cruncher, this bot infects other bots with a small block of code, filling the other bot with this bot's flags. Those bots are then sitting ducks for further attack, but they will be mostly full of my flags when they get re-infected by someone else.

Edit: thanks to @PhiNotPi for golf assistance, @overactor for efficiency advice
> 3 votes

# Answer
# Neutralizer

This bot makes its victim rewrite its entire program, making it worth 0 points. Once the virus is in place, it moves on. This is a scorched earth approach to victory.

```
If D #C+2 #C+3          // A: If [enemy exists] B else C
Copy C+22 C             // GOTO A
If *#*C==#7 #C+4 #C+5   // B: If [enemy was neutralized] D else E
Move                    // C: Move
Copy E D                // D: Turn Randomly
Copy #7 *#*C            // E: Neutralize enemy
Copy C+1 C              // Skip the next line
Copy #C #C+1            // Neutralizing Code [Copy this line to next line]

```

The comparison `*#*C==#7` doesn't seems to adjust for the opponent's shift correctly, but the bot does eventually move on.
> 3 votes

# Answer
# Happy As A Clam

This is an exercise in blocking. It performed remarkably well until `$Copy` came around.

The clam has 22 block commands. Because `A` is shifted every loop, they will reference different lines each time through the loop. This allows each command to stack blocks on every other line, maxing out at 22 blocks per line. Thus, to break the fully armored clam, one would need to write to a line 22 times.

For example, `#10` will be protected each time through the loop by the following lines:

* Loop 0, A=0 `#10` protected by line 7 (`7+0+3`=10)
* Loop 1, A=7 `#10` protected by line 0 (`0+7+3`=10)
* Loop 2, A=14 `#10` protected by line 17 (`17+14+3`=34=10)
* Loop 3, A=21 `#10` protected by line 10 (`10+21+3`=34=10)

So after Line 10 of Loop 3, `#10` has been blocked 4 times, requiring 4 writes to `#10` to break the blocks, with a 5th one to actually overwrite the line.

Note that blocks are keyed by their `C` value and will **not** stack if the protected line was already blocked by the same `C` value. So after 22 blocks are established for each line, the blocks will no longer stack.

```
Block #C+A+3
Block #C+A+3
Block #C+A+3
Block #C+A+3
Block #C+A+3
Block #C+A+3
Block #C+A+3
Block #C+A+3
Block #C+A+3
Block #C+A+3
Block #C+A+3
Block #C+A+3
Block #C+A+3
Block #C+A+3
Block #C+A+3
Block #C+A+3
Block #C+A+3
Block #C+A+3
Block #C+A+3
Block #C+A+3
Block #C+A+3
Block #C+A+3
Copy A+7 A
Flag

```
> 3 votes

# Answer
## MindControl

I guess it's never too late?

```
Block #C+D
If D #2 #0        // Scan for enemy
If *#E==#E #0 #5  // Attack if necessary
Copy D+5 D        // Turn
Copy 22+1 C       // Repeat
Copy 4+1 C        // ATTACK:
Copy #22+1 *#*C   //   Freeze
Copy #17 *#17     //   Upload the DOWNLOADER
Copy #18 *#18     //
Copy #21 *#19     //
Copy D+2 *D       //   FACE ME!!
Copy 17 *C        //   Start download
If E #0 #13
If E #0 #13
Copy 22+1 C
Flag
Flag
Copy *#B+20 #B+20         // DOWNLOADER
If *#B+20==#B+20 *#20 #19 //
Copy 22+1 C               //
Copy 1+B B                //
Copy 16 C                 //
Flag
Copy 23+C C        // FREEZE

```

MindControl comes from my idea that it would take some considerable time to copy my whole program to the opponent, during which my bot is vulnerable to attacks from other directions. So why not make the opponent copy my program while I scan for enemies?

Once it finds an enemy, MindControl immediately freezes the enemy to prevent escape. Then it uploads the downloader to the opponent and let the victim download MindControl's program itself. The downloader exploit the fact that few bots uses `B` and will loop until it downloads all 24 lines. When the downloader rewrites `#19` from `Copy 16 C` to `Copy 23 C`, it signifies the victim have downloaded all lines and will go on to reboot itself.

The first versions of my bot does not include Blocks. And it was so vulnerable that almost any change is crippling. So I decided to add Blocks based on Wasmoo's $Copy (which is based on COTO's Lockheed). The downside I found is that it is difficult for the original to correct mistakes in the copies. But this is far from crippling and the score increased significantly so I kept the Blocks.

## UPDATES

I improved the downloader to keep trying to download until a successful rewrite to circumvent blocks. It does mean it takes one more turn to upload the downloader but my score doubled after this change!! Can't argue with numbers.

---

Another update. As you may have noticed, MindControl decides whether to attack target by comparing a random line between itself and its target. If they match, MindControl just assumes the target is already infected and leave it alone. (Side note: I used to use a static line for comparison but that gives lots of false positives and negatives) Turns out that gives a lot of false negatives. So I decided to exploit `==` and make some trivial changes like `C+23` to `23+C`. The program is functionally identical but different in the eyes of `==`. Now that MindControl has no line that is identical to any line in any other bot, it will 100% hit any untouched bot. Again, score increased significantly.

---

Improved the Downloader again. It now runs on a shorter loop. (which seems to have a large correlation with my score)

---

Improved Downloader yet again. Uses original bot's code so it uploads faster. Also added 2 random blocks which seems to improve score
> 3 votes

# Answer
# Attacker

```
Copy #E *#*C
Copy #E *#*C
Copy #E *#*C
Copy #E *#*C
Copy #E *#*C
Copy #E *#*C
Copy #E *#*C
Copy #E *#*C
Copy #E *#*C
Copy #E *#*C
Copy #E *#*C
Copy #E *#*C
Copy #E *#*C
Copy #E *#*C
Copy #E *#*C
Copy #E *#*C
Copy #E *#*C
Copy #E *#*C
Copy #E *#*C
Copy #E *#*C
Copy #E *#*C
Copy #E *#*C
Copy #E *#*C
Flag

```
> 2 votes

# Answer
# Movebot

```
Move
Copy 23 C
Flag

```

Like Flagbot, but move around while accepting gifts of code to go with all of our flags.
> 2 votes

# Answer
# Magus

Magus is a simple attempt at a self-propagating virus. It attempts to copy itself into the programs of other bots. (Edited to remove negative numbers, fix condition, trim lines.)

```
Block #A
Copy #A *#A
Copy A+1 A
If A #0 #4
Copy 0 *C
Flag
Move
Copy 0 C

```
> 2 votes

# Answer
# Reproducing bot

This bot tries to freeze his opponent and then copy his entire code into that bot before restarting the other bot. This should also work (mostly) if the opponent uses blocking, though that does make it all even slower than it already is.

```
If D #23 #22
Copy 23 C
Copy #18 *#*C
Copy #18 *#*C+1
Copy #18 *#*C
Copy #18 *#0
Copy #18 *#0
Copy 0 *C
Copy 0 *C
Copy 1 A
Copy #A *#*A
If D #12 #14
Copy A+1 A
Copy 9 C
Copy 23 C
Flag
Flag
Flag
Copy C+23 C
Copy D+1 D
Flag
If *#*C==#*C #19 #13
Move
If *#*C+1==#*C+1 #21 #13

```
> 2 votes

# Answer
# Blocker

```
Copy A+1 A
Block #A
Copy C+22 C

```
> 1 votes

# Answer
# Copycat

```
If D #4 #3
Move
Copy 23 C
Copy *#*C #1
Copy #23 *#E

```
> 1 votes

# Answer
# DNAbot

```
Flag
Copy 8 D
Copy 16 B
If #D==#B #C+2 #C+3
Block #A
Copy #D #A
If D #7 #15
Copy #23 *#*C
Copy A+1 A
Copy B+1 B
Copy D+1 D
If #D==#B #C+2 #C+3
Block #A
Copy #D #A
If D #7 #15
Move
Copy A+1 A
Copy B+1 B
Copy D+1 D
If #D==#B #C+2 #C+3
Block #A
Copy #D #A
If D #7 #15
Flag

```

This bot repairs its own code while moving and attacking.
> 1 votes

# Answer
# Block, Freeze, Attack

```
Block #A        // start block loop
Copy A+1 A      // loop A from 0 to 23
If A #3 #4
Copy 23 C       // repeat block loop
Copy 5 C        // exit block loop to attack/move loop
Move
If D #11 #5     // attack or move
Copy A+1 A      // loop A from 0 to 23
If A #9 #10
Copy 5 C        // repeat attack/move loop
Copy 23 C       // exit attack/move loop to block loop
Copy 11 C       // start of attack routine
Copy #23 *#*C   // freeze opponent
Copy #19 *#E    // copy flag to opponent
Copy #20 *#E    // copy flag to opponent
Copy #21 *#E    // copy flag to opponent
Copy #22 *#E    // copy flag to opponent
Copy D+1 D      // change direction
Copy 5 C        // repeat attack/move loop
Flag
Flag
Flag
Flag
Copy C+23 C     // freeze instruction, for copying

```

Blocks all 24 lines, then loops 24 times either moving or attacking, then repeats. An attack involves attempting to freeze the opponent, then copying four flags to random locations, then turning.
> 1 votes

# Answer
# Quick freezerbot

Tries to copy flags in the line that will get executed next of his opponent, moves if there is no enemy to attack.

```
Block #13
Block #14
If D #13 #14
If D #13 #14
If D #13 #14
If D #13 #14
If D #13 #14
If D #13 #14
If D #13 #14
If D #13 #14
If D #13 #14
If D #13 #14
Copy 23 C
If E #15 #16
Move
Copy #23 *#*C
Copy D+1 D

```
> 1 votes

# Answer
# Hide, Block, Attack

This bot is based off of Block Freeze Attack. I changed the placement of some `If` statements to make it more compact allowing me to plant more flags. I also have it run away at the start of a game to buy some time to block.

```
Copy D+1 D
Move           //buy some time by moving to a more secure location
Block #A+2
Copy A+1 A
If A #11 #17
Copy #23 *#E
Copy #22 *#E
Copy #21 *#E
Copy #20 *#E
Copy #19 *#E
Copy D+1 D
Copy 1 C
Move
If D #14 #15
Copy 3 C
Copy 11 C
Copy #18 *#*C
If D #16 #15
Copy C+23 C
Flag
Flag
Flag
Flag
Flag

```
> 1 votes

# Answer
# Roving Virus

```
If D #6 #16
Move
Copy 23 C
Flag
Flag
Flag
Copy 6 C
Copy A+23 A
Copy #A *#A                     //clone previous line to enemy
Copy 23 *C                      //freeze enemy
If A #6 #16                     //loop or turn then continue
Copy 0 *C                       //reboot enemy
Copy 23 C                       //start moving again
Flag
Flag
Flag
Copy D+1 D                      //turn
Flag
Flag
Flag
Flag
Flag
Flag
Copy 22 C                       //freeze instruction

```

This bot wanders until it finds an enemy, then freezes them, replaces all of their code with its own, unfreezes them, then wanders again.
> 1 votes

# Answer
# The common cold

It infects you virtually immediately and you'll spread it around. based on PhiNotPi's Parasite, the common cold checks almost immediately if it can copy its flag over yours. Blocks a random value if it can't. Moves around a bit if there's no opponent.

```
Block #22
If D #8 #5
If D #8 #5
If D #8 #5
Copy 23 C
If E #6 #7
Copy D+1 D
Move
If *#E=#22 #15 #9
If *#E+1=#22 #16 #10
If *#E+2=#22 #17 #11
If *#E+3=#22 #18 #12
If *#E+4=#22 #19 #13
If *#E+5=#22 #20 #14
If *#E+6=#22 #21 #23
Copy #22 *#E
Copy #22 *#E+1
Copy #22 *#E+2
Copy #22 *#E+3
Copy #22 *#E+4
Copy #22 *#E+5
Copy #22 *#E+6
Flag
Block #E

```
> 1 votes

# Answer
# Influenza

This is closely based off of the Common Cold (which was based off my Parasite) with slightly increased speed.

```
Move
Block #23
If D #8 #0
If D #8 #0
If D #8 #0
If D #8 #7
Copy 0 C
Copy D+1 D
If *#E #9 #10
Copy #23 *#E
If *#E+1 #11 #12
Copy #23 *#E+1
If *#E+2 #13 #14
Copy #23 *#E+2
If *#E+3 #15 #16
Copy #23 *#E+3
If *#E+4 #17 #18
Copy #23 *#E+4
If *#E+5 #19 #20
Copy #23 *#E+5
If *#E+6 #21 #22
Copy #23 *#E+6
Block #E
Flag

```
> 1 votes

# Answer
# Rebranding

```
Move
If D #10 #0
If D #10 #0
If D #10 #0
If D #10 #0
If D #10 #0
If D #10 #0
If D #10 #0
If D #10 #0
Copy 0 C
If *#E=#14 #11 #9
If *#E==#14 #13 #12
Copy D+1 D
Copy #14 *#E
Flag

```

This bot tries to randomly locate flags in enemy bots and replace them with friendly flags, turning away after detecting success. Inspired by Cancer bot.
> 1 votes

# Answer
# RandomCopier

```
Move
Copy #E *#*E
Copy E D
Copy 23 C

```
> 0 votes

# Answer
# Rush, Attack, Dodge

```
Move
Move
If D #5 #1
Copy E D
Copy 1 C
Copy #E *#*C
Flag

```

This bot moves or attacks every three turns, changing direction at random.
> 0 votes

# Answer
# Forward Clone

```
Move
Move
If D #4 #1
Copy 1 C
Copy #E *#E
Flag

```

This bot moves or attacks every two turns, randomly cloning itself into any bot it bumps into.
> 0 votes

# Answer
# Fast Forward Clone

```
Move
If D #7 #0
If D #7 #0
If D #7 #0
If D #7 #0
If D #7 #0
Copy 1 C
Copy #E *#E
Flag

```

This bot moves or copies itself five out of six turns.
> 0 votes

# Answer
# Fast Move Clone Dodge

```
Move
If D #8 #0
If D #8 #0
If D #8 #0
If D #8 #0
If D #8 #0
Copy D+1 D
Copy 23 C
Copy #E *#E
Flag

```

This bot moves or copies its flags five out of seven turns, changing direction every seven turns.
> 0 votes

# Answer
# Quick Freeze!

Quickly move to plant your flag in other bots, making sure that you completely stop them in their tracks.

```
Move
If D #2 #6
Copy #8 *#*C
Copy #7 *#*C+21
Block *#*C+20
Copy E D
Copy 23 C
Flag
Copy #C+23 #C+1
Flag
Flag
Flag
Move
If D #14 #18
Copy #20 *#*C
Copy #19 *#*C+21
Block *#*C+20
Copy E D
Copy 11 C
Flag
Copy #C+23 #C+1
Flag
Flag
Flag

```
> 0 votes

# Answer
# Boring copybot

I'm under the impression that having more lines of code makes my bot more robust. I'm also blocking my C variable often to prevent easy attacks. The idea is that other bots encounter me and I fill them with my flag and copy commands. I'm also hoping that considering the straightforward way my code works copying lines of my code into enemies will actually make them behave like my bot.

```
Block C
If D #C #C+1
Copy #E *#*E
Move
Flag
Copy #E *#*E
Block C
If D #C #C+1
Copy #E *#*E
Move
Flag
Copy #E *#*E
Block C
If D #C #C+1
Copy #E *#*E
Move
Flag
Copy #E *#*E
Block C
If D #C #C+1
Copy #E *#*E
Move
Flag
Copy #E *#*E

```
> 0 votes

# Answer
# Nanoviris

This is a really small virus.

```
Copy #A *#A
Copy A+1 A
If A=7 #5 #4
Copy 0 A
Copy 23 C
Copy 0 *C

```
> 0 votes

# Answer
# Kung Fu Bot

```
Copy 20 A
If D #5 #6
If D #11 #6
If D #10 #6
Copy 23 C
Move
If D=*D #7 #8
Copy #9 *#*C
Copy #A *#*C
Copy *#*A #C
If C=3 #5 #4
Copy D+1 D

```

Why give them flags when you could program them to take yours?
> 0 votes

# Answer
# Cancer

This bot hits you hard at first by freezing you as quicky as possible, then replaces all of your flags by his (if possible) and then lets you go again with most of your code intact.

```
If D #4 #12
If D #4 #12
If D #4 #12
Copy 23 C
If *#*C==#23 #5 #6
Copy 6 C
Copy #23 *#*C
Copy 0 A
If *#A=#22 #14 #15
Copy A+1 A
If D #16 #11
Copy 7 C
Copy #22 *#A
Block #E
If A #15 #11
Copy 15 C
Copy #22 *#*C
Copy D+1 D
Copy 23 C
Flag
Flag
Flag
Flag
Copy C+23 C

```
> 0 votes

# Answer
# Flag Injector

Finds an opponent, then inserts its flag to stun the opponent until it looks like a FlagBot. Will move on after several attacks.

Attack redundancy included in an attempt to be more resistant to damage

```
Copy E D     //A: Turn Randomly
Move         //B: Move
If D #10 #3  //C: If [enemy exists] E else D
Copy 0 C     //D: Goto B
Flag
Copy #4 *#*C+1 //ATK1: Copy my flag
Flag
Copy #6 *#*C+1 //ATK2: Copy my flag
Flag
Copy #8 *#*C+1 //ATK3: Copy my flag
Copy 11 C    //E: Goto ATTACK
Copy 23 C    //F: Goto A
If *#*C==#4 #11 #5 //ATTACK: If [enemy executing my flag] E else ATK1
If *#*C==#4 #11 #7 //If [enemy executing my flag] E else ATK2
If *#*C==#4 #11 #9 //If [enemy executing my flag] E else ATK3
If *#*C==#4 #11 #5
If *#*C==#4 #11 #7
If *#*C==#4 #11 #9
If *#*C==#4 #11 #5
If *#*C==#4 #11 #7
If *#*C==#4 #11 #9
If *#*C==#4 #11 #5
If *#*C==#4 #11 #7
If *#*C==#4 #11 #9

```
> 0 votes

# Answer
# TurretMaker

```
Move
If D #4 #0
If D #4 #0
Copy 0 C
Copy 4 C
If D #12 #11
If D #12 #11
If D #12 #11
If D #12 #11
If D #12 #11
Copy D+1 D
If D #4 #3
Copy #C+8 *#*C
Copy #C+23 *#E
Copy D+1 D
Flag
If D #C+21 #C+22
Copy C+22 C

```

When this bot bumps into another bot it turns that bot into a "turret". Turrets spin in place and copy a flag into any adjacent bots.
> 0 votes

# Answer
## Nullifier

In the hope that I finally understood the specs (and that no one did the same bot already):

```
Move
If D #2 #11
If *A #4 #3
Copy 0 *A
If *B #6 #5
Copy 0 *B
If *C #8 #7
Copy 23 *C
If *#0==#11 #12 #9
Copy #11 *#0
Copy 12 C
Copy 23 C
Copy #15 *#E
Copy 12 C
Flag

```

This bot, hopefully, move toward an opponent, then attempt to set this opponent's A, B and C to 0, then to copy `Copy 23 C` to its 0th line. Then write a flag in random lines in a loop.
> 0 votes

# Answer
# Palimpseste

```
Move
If D #3 #2
Copy 23 C
Copy 3 C
If *#A=#23 #5 #6
If *#A==#23 #6 #9
Copy 6 C
Copy A+23 A
Copy 3 C
Copy 9 C
Copy #23 *#A
If A #8 #12
Copy 12 C
Copy D+1 D
Copy 23 C

```

Slowly rewrite the flags on the opponent as its own flag, do not touch the other lines, and then move on to another opponent. Very slow as it takes 3 turns for each controlled line whether it does rewrite or not.
> 0 votes

# Answer
# Adaptive bot

I've noticed that quick, simple tactics seem to work well since bots are packed closely. If you spend too much time standing still, you're done. This bot starts out with a freeze and tag tactic but switches to making other bots freeze and tag bots after the first time a both his and the other bots E value are zero. He is rather fragile though, so we'll see how he does.

**Edit:** I've managed to decrease the lines needed and thus managed to throw in some line blocking for both the original as well as the clone, the advanced mode now also copies itself fully instead of just the simple part.

```
If D #C+10+B #C+8
Copy C+22 C
Flag
Copy C+23 C
Move
Copy D+3 D
Copy #C+3 *#*C
Copy #C+2 *#*E
If E #C+15 #C+16
If E #C+5 #C+7
If E=0 #C+11 #C+12
If *E=0 #C+13 #C+12
If *#*C==#C+3 #C+9 #C+6
Copy 7 B
Copy C+21 C
If E #C+4 #C+5
Block #E
If *#*C==#C+3 #C+15 #C+6
Copy C+15 C
Copy 23 A
Copy D *D
Copy #A *#*C+A
Copy A+23 A
If A=23 #C+6 #C+14

```
> 0 votes

# Answer
# Kamikaze

```
If D #7 #6
If D #7 #6
If D #7 #6
If D #7 #6
If D #7 #6
Copy 23 C
Block #C+A
If *#0==#6 #8 #9
Copy #5 *#0
If *#21=#10 #11 #12
Flag
If *#21==#10 #15 #12
If *#22=#10 #13 #14
If *#22==#10 #16 #17
Copy #10 *#21
Copy #10 *#22
Copy #10 *#C

```

The only reason for this is to defeat 3 of the biggest competitors:`AttackOrElse`, `Byzantine` and `SuperFreeze`
> 0 votes

---
Tags: king-of-the-hill
---


title: Penalty Shootout

text:
# Question
Title: Penalty Shootout
# Penalty shootout

Welcome to CG world cup. Your job: Code a penalty shooter and goal keeper!

---

## Rules of the game:

The goal is 700 cm wide and 200 cm tall. If I have to make a rectangle out of it, the goal is ABCD where A is `(0,0)`, B is `(0,200)`, C is `(700,200)`, D is `(700,0)`.

The shooter gives me the coordinate where he will aim. However... there is wind, so your ball final destination may be modified up to 50 positive or negative.

Here's what I'm trying to say...

```
windX= randint(-50,50)
windY= randint(-50,50)
theFinalCoordinateOfTheBallX= coordinateThatBotGiveX + windX
theFinalCoordinateOfTheBally= coordinateThatBotGivey + windY

```

The goal keeper gives me the coordinate where he aims. If the distance of the ball final coordinate and the coordinate of the goal keeper is less then 50 cm (using Pythagoras), the ball is saved by the keeper, otherwise it's a goal.

(Note: It is very possible that you did not make a goal, because you MISS the goal. This is possible due to the wind factor. So aiming for (0,0) is not really good idea.)

Each of you has 10 attempts to become goal keeper and shooter.

---

## Communication protocol:

You will receive this from STDIN

> R Sx Sy Gx Gy

`R`-\> Round # (Starts from 1 to 10)

`Sx` -\> The x coordinate where the opponent aim when they shoot in previous round (Seperated by comma)

`Sy` -\> The y coordinate where the opponent aim when they shoot in previous round (Seperated by comma)

`Gx` -\> The x coordinate where the oppenent aim when they are goal keeper in the previous round (Seperated by comma)

`Gy` -\> The y coordinate where the opponent aim when they are goal keeper in previous round (Seperated by comma)

Example:

> 3 57,81 29,90 101,50 27,85

Meaning

This is round 3
In round 1: When your opponent is shooter: He aims for `(57,29)`. In round 2 he aims for `(81,90)`
In round 1: When your opponent is goal keeper. He aims for (101,27). In round 2 he aims for `(50,85)`

Another example:

> 1

This is round 1
No game yet! Prepare your bot for this kind of situation!

Your bot, must give me from STDOUT this:

> Sx Sy Gx Gy

`Sx` -\> My x coordinate of where do I aim when I'm the shooter this round.

`Sy` -\> My y coordinate of where do I aim when I'm the shooter this round.

`Gx` -\> My x coordinate of where do I am when I'm the goal keeper this round.

`Gy` -\> My y coordinate of where do I am when I'm the goal keeper this round.

Example:

> 81 25 71 98

This means you aim for `(81,25)` when shooting and `(71,98)` when become goal keeper.

### All numbers that you will receive is integer. Your program must output integer too. Floating number is not tolerated

---

## Deciding champion:

Win worths 3 points. Draw worths 1 point. Lost is a null.

After single-round robin, The 4 top high scoring bot will do double-round robin. Among this 4 bots, the champion will be crowned.

---

## Technical details:

The program runs on Windows 7, using Python 2.7.2

Unfortunately, due to my programming skill, I can only receive entry from Python and C. (To Java users, my deepest apology) I'm confident that I can accept entry from C++ and Fortran. I will try when someone gives me a submission in that language...

C programs will be compiled *manually* using this command:

> gcc programFile.c -o programFile

The same thing occurs to Fortran and C++, but since I haven't try, I'm not sure what precisely is the command.

Note: Since using Python 2.7.2, you may want to use `raw_input` instead of `input`

Your program may not use/modify/access external source. (Internet, environment variable, making file, accessing folder, external number, etc)

## Your program must be deterministic, and please dont over kill random() =p

You may make multiples entry, but please dont help each other..

Make sure you give your bot a name...

---

## FAQ:

> Q: Is goals inclusive or exclusive?

A: **Inclusive.** So if your ball lands at `(0,0)` and it's out of the goal keeper's reach, it's counts as a goal. (Well irl, it will hit the post)

> Q: What is the time limit?

A: **1 second**

> Q: What happened if my ball ends at (x,-y)

A: **No goal** Well, irl you cant aim downwards below the ground.

> Q: But can my program outputs negative number?

A: **Absolutely**

> Q: Any controllers so I can train my bot?

A: **Here**

> Q: Does my program run 'on and off' or it will keep running until it gets and EOF?

A: **On and off** On a new round, I will call your bot and pass the necessary info. After you gave my your coordinate, it's done job.

---

Good luck, you will need it..

# Answer
## RandomBot, Python

```
from random import seed,randint
seed(raw_input())
print "%d %d %d %d" % (randint(50,650), randint(50,150), randint(50,650), randint(50,150))

```

As long as there are no predictable bots to beat, I believe this should be fairly optimal (of course, you could just seed the PRNG yourself to figure out what I'll be doing, but writing a bot to specifically kill one other bot isn't exactly sportsmanship, right? ;)). Obviously, this isn't good at catching, but without anyone to beat, I can't tell how to predict them.
> 5 votes

# Answer
## Center, Python

This bot acts just as I would: It stays in the center when being the goal keeper (jumping is hard), and when shooting it does the exact opposite: it aims for one of the corners.

It doesn't care what happened in previous rounds and thus is a good victim for bots that do take this information into consideration.

```
import random
random.seed(raw_input())
corners = [[50,50],[50,150],[650,50],[650,150]]
corner = random.choice(corners)
print "%d %d %d %d" % (corner[0], corner[1], 350, 100)

```
> 4 votes

# Answer
## Averager (Python)

This is my second serious answer on this site and my first KOTH. Be kind, good sirs.

Yes. The code looks pretty.

```
rl = lambda l: map(int, l.split(","))
avg = lambda l: sum(l)/len(l)

def take_input():
    r = raw_input()
    t = True if len(r.split()) == 1 else False
    (rno, sx, sy, gx, gy) = (r,'0','0','0','0') if t else r.split()
    return (int(rno),) + tuple(map(rl, [sx, sy, gx, gy]))

def g(d):
    return((avg(d[1]) + 350)/2, (avg(d[2]) + 100)/2)

def s(d):
    return (abs((avg(d[3]) - 350)/2), abs((avg(d[4]) - 100)/2))

def out(d):
    print "%d %d %d %d" % (s(d) + g(d))

out(take_input())

```

Halp and tast k?
> 3 votes

# Answer
## CenteredRandom (Python)

```
from random import randint, seed, choice

rl = lambda l: map(int, l.split(","))
avg = lambda l: sum(l)/len(l)
avg2 = lambda l, x: avg(l[:-x]) if x < len(l) else avg(l)

corners = choice([[50,50],[50,150],[650,50],[650,150]])

def take_input():
    r = raw_input()
    seed(r)
    t = True if len(r.split()) == 1 else False
    (rno, sx, sy, gx, gy) = (r,'0','0','0','0') if t else r.split()
    return (int(rno),) + tuple(map(rl, [sx, sy, gx, gy]))

def enemy_is_center(d):
    return len(d[3]) > 2 and len(d[4]) > 2 and d[3][-2:] == [350, 350] and d[4][-2:] == [100, 100]

def s(d):
    return (100,100) if enemy_is_center(d) else (randint(50, 650), randint(50, 150))

def g(d):
    return (corners[0], corners[1]) if enemy_is_center(d) else (randint(50, 650), randint(50, 150))

def out(d):
    print "%d %d %d %d" % (s(d) + g(d))

out(take_input())

```
> 2 votes

---
Tags: king-of-the-hill
---


# Question
Title: Display the mouse pointer trails... of the future!
Inspired by this example of using d3js, I challenge you to create a canvas (or your language-of-choice equivalent) in which the mouse pointer trails will be displayed, with the following twist:

# The Twist

You should not display the trails of where the mouse pointer **was**, but the "trails" of where it **will** (might) be in future.

You can do it by using either:

1. A time machine, or
2. Probabilistic estimations based on previous mouse movements

# Assumptions

In case you didn't choose the time machine implementation, when the mouse does not move for more than *threshold* milliseconds, you can display none of the trails. (The *threshold* value is up to you to choose).

The cursor image is up to you and does not have to be the same of the OS's cursor (you can even draw a plain small circles or dots).

No evil input will be tested: You can assume the movements are smooth. 'Smooth' definition for this case is: if the mouse movements were a function over the x and y axis of the canvas - it would be a continuous function.

# Winning

The valid answer with the least characters in code will win. In case of a tie - the one that was posted first will win.

**EDIT:** The valid answer with the **most upvotes** will win. In case of a tie - the one that was posted first will win. You can be creational on the implementation, or be precise with the prediction. I'm not the judge anymore, we all are :)

* A valid answer must include a way for me to play with (test! I meant test), either on an online tool or on a freely-downloadable compiler/interpreter/runtime/etc.

# Answer
> 33 votes
# Javascript

My program predicts the direction of the pointer by using the average of the angular change in direction of the last 20 mouse moves. It also uses the variance of the angular change to create a "cloud" of possible locations and directions of the pointer. The color of each pointer in the "cloud" is supposed to represent the likelihood of it being the new position of the mouse pointer, where darker colors represents a greater likelihood. The distance of the pointer cloud ahead of the mouse is calculated using the speed of mouse movement. It doesn't make the best predictions but it looks neat.

Here's a fiddle: http://jsfiddle.net/5hs64t7w/4/

Increasing the size of the pointer cloud is interesting to see. It can be set by changing the `cloudSize` variable on the first line of the program. Here is a fiddle with a cloud size of 10: http://jsfiddle.net/5hs64t7w/5/

I used these sources to get formulas for circular mean and variance:
Circular Mean: http://en.wikipedia.org/wiki/Circular\_mean
Circular Variance: http://www.ebi.ac.uk/thornton-srv/software/PROCHECK/nmr\_manual/man\_cv.html

Here is the code if anyone is interested:

```
    var cloudSize = 3;

    var canvas = document.getElementById('canvas_element');
    var c = canvas.getContext('2d');
    var prevX = -1;
    var prevY = -1;
    var curX = -1;
    var curY = -1;
    var distance = 0;
    var direction = 0;

    function drawMouse(x, y, angle, gray){
        var grayVal = Math.round(gray*255);
        var grayString = "rgb(" + grayVal + "," + grayVal +"," + grayVal + ")";
        c.fillStyle = grayString;
        c.strokeStyle = grayString;
        c.lineWidth = 1;
        c.beginPath();
        c.moveTo(x, y);
        c.lineTo(x + 16*Math.cos(angle + Math.PI/2.0 + Math.PI/8.0), y + 16*Math.sin(angle + Math.PI/2.0 + Math.PI/8.0));
        c.moveTo(x, y);
        c.lineTo(x + 16*Math.cos(angle + Math.PI/2.0 - Math.PI/8.0), y + 16*Math.sin(angle + Math.PI/2.0 - Math.PI/8.0));
        c.lineTo(x + 16*Math.cos(angle + Math.PI/2.0 + Math.PI/8.0), y + 16*Math.sin(angle + Math.PI/2.0 + Math.PI/8.0));
        c.stroke();
        c.fill();
        c.beginPath();
        c.moveTo(x, y);
        c.lineTo(x + 24*Math.cos(angle + Math.PI/2), y + 24*Math.sin(angle + Math.PI/2));
        c.stroke();
    }

    function sum(array){
        var s = 0.0;
        for(var i=0; i<array.length; i++){
            s += array[i];
        }
        return s;
    }

    var sins = [];
    var coss = [];
    var lengths = [];
    var times = [];
    var index = 0;
    var limit = 20;
    var variance = 0;
    var prevTime = new Date().getTime();
    function updateDistanceAndDirection(x, y){
        var angle = Math.atan2(prevY - curY, prevX - curX);
        sins[index] = Math.sin(angle);
        coss[index] = Math.cos(angle);
        lengths[index] = Math.sqrt((curX-prevX)*(curX-prevX) + (curY-prevY)*(curY-prevY));
        var time = new Date().getTime();
        times[index] = time - prevTime;

        variance = 1.0 - Math.sqrt(sum(coss)*sum(coss)+sum(sins)*sum(sins))/sins.length;

        direction = Math.atan2(1/sins.length*sum(sins),1/coss.length*sum(coss));
        var speed = sum(lengths)/(sum(times)/200);
        distance = Math.min(Math.max(40, speed), 100);
        prevTime = time;
        index = (index+1)%limit;
    }

    function drawMice(count){
        c.clearRect(0, 0, canvas.width, canvas.height);

        for(var i=count; i>=0; i--){
            var dir = direction + i*variance;
            drawMouse(curX - distance*Math.cos(dir), curY - distance*Math.sin(dir), dir - Math.PI/2, i/count);
            dir = direction - i*variance;
            drawMouse(curX - distance*Math.cos(dir), curY - distance*Math.sin(dir), dir - Math.PI/2, i/count);
        }
    }

    canvas.onmousemove = function (event) {
        curX = event.clientX;
        curY = event.clientY;

        updateDistanceAndDirection(curX, curY);

        drawMice(cloudSize);

        prevX = curX;
        prevY = curY;
    };

```

# Answer
> 14 votes
# Java

I decided to take the time machine approach. It turns out the key ingredient of a time machine is java.awt.Robot. My program lets you move your mouse around for 10 seconds. After the 10 seconds it goes back in time and recreates your mouse movement, while predicting it perfectly.

Here's the code:

```
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.Robot;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.MouseEvent;
import java.awt.event.MouseMotionListener;
import java.util.ArrayList;
import java.util.TimerTask;

import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.Timer;

public class TimeMachine extends JPanel implements MouseMotionListener {

    Timer timer;
    int time = 10;
    java.util.Timer taskTimer;
    ArrayList<Point> mousePoints;
    ArrayList<Long> times;
    Robot robot;
    int width, height;
    ArrayList<Point> drawMousePoints;

    public TimeMachine(){
        width = 500;
        height = 500;
        drawMousePoints = new ArrayList<Point>();

        robot = null;
        try{
            robot = new Robot();
        }
        catch(Exception e){
            System.out.println("The time machine malfunctioned... Reverting to 512 BC");
        }
        mousePoints = new ArrayList<Point>();
        times = new ArrayList<Long>();

        taskTimer = new java.util.Timer();

        ActionListener al = new ActionListener(){
            public void actionPerformed(ActionEvent e){
                time--;
                if(time == 0)
                    rewind();
                repaint();
            }
        };
        timer = new Timer(1000, al);
        start();
    }

    public void paint(Graphics g){
        g.clearRect(0, 0, width, height);
        g.drawString("Time Machine activiates in: " + time, 15, 50);
        for(int i=0; i<drawMousePoints.size(); i++){
            Point drawMousePoint = drawMousePoints.get(i);
            drawMouse(drawMousePoint.x-getLocationOnScreen().x, drawMousePoint.y-getLocationOnScreen().y, g, Color.BLACK, Color.LIGHT_GRAY, (double)i/drawMousePoints.size());
        }
    }

    public void drawMouse(int x, int y, Graphics g, Color line, Color fill, double alpha){
        Graphics2D g2d = (Graphics2D)g;
        g2d.setColor(new Color(fill.getRed(), fill.getGreen(), fill.getBlue(), (int)Math.max(Math.min(alpha*255, 255), 0)));
        g2d.fillPolygon(new int[]{x, x, x+4, x+8, x+10, x+7, x+12}, new int[]{y, y+16, y+13, y+20, y+19, y+12, y+12}, 7);

        g2d.setColor(new Color(line.getRed(), line.getGreen(), line.getBlue(), (int)Math.max(Math.min(alpha*255, 255), 0)));
        g2d.drawLine(x, y, x, y + 16);
        g2d.drawLine(x, y+16, x+4, y+13);
        g2d.drawLine(x+4, y+13, x+8, y+20);
        g2d.drawLine(x+8, y+20, x+10, y+19);
        g2d.drawLine(x+10, y+19, x+7, y+12);
        g2d.drawLine(x+7, y+12, x+12, y+12);
        g2d.drawLine(x+12, y+12, x, y);
    }

    public void start(){
        timer.start();
        prevTime = System.currentTimeMillis();
        mousePoints.clear();
    }

    public void rewind(){
        timer.stop();
        long timeSum = 0;
        for(int i=0; i<times.size(); i++){
            timeSum += times.get(0);
            final boolean done = i == times.size()-1;
            taskTimer.schedule(new TimerTask(){
                public void run(){
                    Point point = mousePoints.remove(0);
                    drawMousePoints.clear();
                    drawMousePoints.addAll(mousePoints.subList(0, Math.min(mousePoints.size(), 30)));
                    robot.mouseMove(point.x, point.y);
                    repaint();
                    if(done)
                        System.exit(0);
                }
            }, timeSum);
        }
    }

    long prevTime = 0;
    public void record(MouseEvent m){
        if(timer.isRunning()){
            long time = System.currentTimeMillis();
            mousePoints.add(new Point(m.getXOnScreen(), m.getYOnScreen()));
            times.add((time-prevTime)/10);
            prevTime = time;
        }
    }

    public static void main(String[] args){

        TimeMachine timeMachine = new TimeMachine();

        JFrame frame = new JFrame("Time Machine");
        frame.setSize(timeMachine.width, timeMachine.height);
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setVisible(true);
        frame.addMouseMotionListener(timeMachine);

        frame.add(timeMachine);
    }

    public void mouseDragged(MouseEvent m) {
        record(m);
    }

    public void mouseMoved(MouseEvent m) {
        record(m);
    }

}

```

# Answer
> 10 votes
# Vanilla Javascript

Just to get things started, here is a simple prediction based on two values. The last `n` mouse postions are memorized and kept in a queue, the prediction is a simple linear extrapolation of the first and last element in the queue.

This is just the prediction code, the full code including the demo can be seen in `this fiddle`:

```
function predict(trail) {
    var b = trail.pop(),
        a = trail[0],
        d = {
            x: b.x - a.x,
            y: b.y - a.y
        },
        m = Math.sqrt( d.x * d.x + d.y * d.y );

    d.x = 5 * d.x / m;
    d.y = 5 * d.y / m;

    var predictions = [];
    for(var i = 1; i <= 10; i++) {
        predictions.push({
            x: b.x + i * d.x,
            y: b.y + i * d.y
        });
    }

    return predictions;
}

```

The demo contains a comment in the prediction that allows you to instead use the last two elements in the queue for the prediction. Makes the result more "real-time", but also less "smooth".

If anyone wants to use the `boilerplate work` to implement a different prediction algorithm, feel free. It's not a lot of work anyway.

# Answer
> 4 votes
**Javascript**

*The past is the best prediction for the future* \- me, and propably someone else too

My solution is very simple. First, here is the \>\>\> Fiddle! \<\<\<

All it does is shifting the past trail, so it looks like the future trail. Basically no Math is involved (I Know, pretty boring). You can easily see the errors, especially when moving the cursor in circles. That's why I made the trail so short ;)

The code:

```
<!DOCTYPE html>
<html>
    <head>
        <style type="text/css">
            .cursor {
                width: 12px;
                height: 19px;
                position: absolute;
                background-image: url(https://i.imgur.com/h8imKBP.png);
            }
        </style>
        <script type="text/javascript">

            var x, y;
            window.onmousemove = function(e) {x=e.clientX; y=e.clientY;}

            var p = [0,0,0,0,0,0,0,0,0,0];
            window.setInterval(function() {
                p.shift();
                p.push([x, y]);
                var diff = [x-p[0][0], y-p[0][1]];
                for (var i = 0; i < 10; i++) {
                    var e = document.getElementById(i);
                    e.style.left = (p[9-i][0]+diff[0])+"px";
                    e.style.top = (p[9-i][1]+diff[1])+"px";
                }
            }, 10);

        </script>
    </head>
    <body>
    <div id="0" class="cursor"></div>
    <div id="1" class="cursor"></div>
    <div id="2" class="cursor"></div>
    <div id="3" class="cursor"></div>
    <div id="4" class="cursor"></div>
    <div id="5" class="cursor"></div>
    <div id="6" class="cursor"></div>
    <div id="7" class="cursor"></div>
    <div id="8" class="cursor"></div>
    <div id="9" class="cursor"></div>
    </body>
</html>

```

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


title: Electron Configurations

text:
# Question
Title: Electron Configurations
# Electron Configurations

Your mission is to accept an element's atomic number as input, and output its electron configuration (e.g. `2,8,8,2` for calcium).

## Input

An atomic number from 1 to 118. You may assume valid input. The atom is not charged (it has as many electrons as protons). You may not expect the input to be stored in a variable, and you must write a complete program.

## Output

The number of electrons in each non-empty electron shell. I will be quite lenient with the output format; all of the following are acceptable, i.e. you may use any punctuation or whitespace to separate the numbers, and brackets of any sort are permitted. Please specify which is used.

* `2,8,8,2`
* `2.8.8.2`
* `2, 8, 8, 2,`
* `[2,8,8,2]`
* `2 8 8 2`
* `([2 [8]] [8] 2)`

## How Electrons Work

In atoms, electrons are ordered into "shells", which are energy levels. Each shell has a certain capacity, the maximum number of electrons that it is capable of holding. The shells are filled from the inside out, but not evenly. Your task is to determine, given an atomic number, how many electrons there are in each shell, according to this source.

Up to and including calcium (atomic number 20), the shells fill evenly and in order; the inner shell is first filled to its capacity of 2, the second to 8, then the third to 8 and the last to 2. The electron configuration of calcium is `2,8,8,2`.

After calcium, things get complicated; further electrons go into the third shell, not the last one. To make things worse, vanadium (23) is `2,8,11,2`, while chromium (24) is `2,8,13,1` and manganese (25) is `2,8,13,2`.

There are some consistent patterns, however: a noble gas and the seven elements before it will always have the number of electrons in the outer shell increase from 1 to 8. For example:

* gold (79): `2,8,18,32,18,1`
* mercury (80): `2,8,18,32,18,2`
* ...
* astatine (85): `2,8,18,32,18,7`
* radon (86): `2,8,18,32,18,8`

## Rules

* Standard loopholes are forbidden.
* Libraries which existed prior to this challenge are permitted.
* Any built-in or library features which specifically deal with atoms, molecules or chemistry are banned.
* Lowest code length in bytes wins.
* In the linked source, configurations of elements 103-118 are marked with *(?)*, as they are predicted, and the elements are too unstable for this to be checked. For this challenge, assume them to be correct.
* You may hardcode part or all of your data.
* **\[NEW RULE\]** Please provide a base64 or an xxd dump of your files if you use control characters in them (as many answers seem to be doing)

**WINNER: Dennis's CJam answer at 80 bytes!**

# Answer
# CJam, ~~87~~ ~~83~~ ~~82~~ 80 bytes

```
0"hTHøìð¼Ä¿håêÛ¾ªÔ¼"256b6b5a/4a8**li<{[33:B_B*65_B*1]=\_B%8=B\#*+}/Bb0-`

```

The above code contains unprintable characters.

Try it online in the CJam interpreter. If the link doesn't work for you, copy from this paste.

### Background

To obtain the electron configuration of the *Nth* atom, we start with an atom without electrons and apply *N* transformations to it.

To reduce the byte count of the implementation, we represent the electron configuration of an atom as an integer. Each digit of that integer in base 33 corresponds to the number of electrons in a certain shells; the least significant digit represents the outer shell.

For example, the electron configuration of Molybdenum (42) is **\[2 8 18 13 1\]**. This corresponds to the integer **2 × 334 \+ 8 × 333 \+ 18 × 332 \+ 13 × 33 + 1 = 26,79,370**.

Palladium (48) is a special case, which we treat as **\[2 8 18 18 0\]** instead of **\[2 8 18 18\]**.

This convenient representation reduces the aforementioned transformations to simple arithmetic:

* `R += 1` (add an electron to the outer shell)
* `R += 33` (add an electron to the second outer shell)
* `R += 65` (add two electrons to the second outer shell; remove one from the first)
* `R += 1089` (add an electron to the third outer shell)
* `R += 2145` (add two electrons to the third outer shell; remove one from the second)
* `R *= 33, R += 1` (add a new shell containing a single electron)

All that's left is to somehow encode which transformation has to be applied to pass from a particular atom to the next. The differences of the integer representations of two consecutive atoms are as follows:

```
[1 1 65 1 1 1 1 1 1 1 2369 1 1 1 1 1 1 1 78401 1 33 33 33 65 1 33 33 33 65 1 1 1 1 1 1 1 2598017 1 33 33 65 33 1 65 33 65 1 1 1 1 1 1 1 1 85745345 1 33 1089 2145 1089 1089 1089 1089 33 2145 1089 1089 1089 1089 1089 33 33 33 33 33 33 33 65 33 1 1 1 1 1 1 1 2830095041 1 33 33 2145 1089 1089 2145 1089 33 2145 1089 1089 1089 1089 1089 65 1 33 33 33 33 33 33 65 1 1 1 1 1 1 1]

```

The unique differences in this array are the following:

```
[1 33 65 1089 2145 2369 78401 2598017 85745345 2830095041]

```

All but the first 5 correspond to instances when a new shell is added; these can be omitted since multiplying by 33 and adding 1 yields the same result as adding the difference.

Since we have to add a new shell if and only if the current atom has exactly eight electrons in its outer shell (with the exception of **He (2) ↦ Li (3)**, which can be encoded as *add 65*), we can encode those transformations as *add 1* and determine the need for multiplication on the fly.

Thus, if we define

```
X := 0
I := 0
L := [33 1089 65 2145 1]
T := [1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 3 1 0 0 0 3 1 1 1 1 1 1 1 1 1 0 0 3 0 1 3 0 3 1 1 1 1 1 1 1 1 1 1 0 2 4 2 2 2 2 0 4 2 2 2 2 2 0 0 0 0 0 0 0 3 0 1 1 1 1 1 1 1 1 1 0 0 4 2 2 4 2 0 4 2 2 2 2 2 3 1 0 0 0 0 0 0 3 1 1 1 1 1 1 1]

```

the electron configuration of the *Nth* atom can be computed as follows:

```
while(X < N):
    R *= (33 ** (R % 33 == 8))
    R += L[T[X]]
    X += 1

```

### How it works

```
" Push 0, the initial value of R; convert the following array into an integer by
  considering it a base 256 number, then back to the array of its digits in base 6.       ";

0"hTHøìð¼Ä¿håêÛ¾ªÔ¼"256b6b

" Replace each 5 in the resulting array by [4 4 4 4 4 4 4 4]. This yields the array T
  from the above section.                                                                 ";

5a/4a8**

" Read an integer N from STDIN and discard all but the first N elements of T.             ";

li<

" For each element Y of the remainder of T, do the following:                             ";

{
    [33:B_B*65_B*1]=\   " Define B := 33, push L, retrieve L[Y] and swap it with R.       ";

    _B%8=B\#*           " Execute R *= 33 ** (R % 33 == 8).                               ";

    +                   " Execute R += L[Y].                                              ";
}/

" Convert R into the array of its digits in base 33, remove eventual zeros (Palladium)
  and replace the resulting array with its string representation.                         ";

Bb0-`

```

### Example run

```
$ base64 -d > electrons.cjam <<< MCJoVEgM+OzwErzEGL9o5erbvqrUB4YZhrwRIjI1NmI2YjVhLzRhOCoqbGk8e1szMzpCX0IqNjVfQioxXT1cX0IlOD1CXCMqK30vQmIwLWA=
$ cksum electrons.cjam
3709391992 80 electrons.cjam
$ for i in {1..118}; do LANG=en_US cjam electrons.cjam <<< $i; echo; done
[1]
[2]
[2 1]
[2 2]
[2 3]
[2 4]
[2 5]
[2 6]
[2 7]
[2 8]
[2 8 1]
[2 8 2]
[2 8 3]
[2 8 4]
[2 8 5]
[2 8 6]
[2 8 7]
[2 8 8]
[2 8 8 1]
[2 8 8 2]
[2 8 9 2]
[2 8 10 2]
[2 8 11 2]
[2 8 13 1]
[2 8 13 2]
[2 8 14 2]
[2 8 15 2]
[2 8 16 2]
[2 8 18 1]
[2 8 18 2]
[2 8 18 3]
[2 8 18 4]
[2 8 18 5]
[2 8 18 6]
[2 8 18 7]
[2 8 18 8]
[2 8 18 8 1]
[2 8 18 8 2]
[2 8 18 9 2]
[2 8 18 10 2]
[2 8 18 12 1]
[2 8 18 13 1]
[2 8 18 13 2]
[2 8 18 15 1]
[2 8 18 16 1]
[2 8 18 18]
[2 8 18 18 1]
[2 8 18 18 2]
[2 8 18 18 3]
[2 8 18 18 4]
[2 8 18 18 5]
[2 8 18 18 6]
[2 8 18 18 7]
[2 8 18 18 8]
[2 8 18 18 8 1]
[2 8 18 18 8 2]
[2 8 18 18 9 2]
[2 8 18 19 9 2]
[2 8 18 21 8 2]
[2 8 18 22 8 2]
[2 8 18 23 8 2]
[2 8 18 24 8 2]
[2 8 18 25 8 2]
[2 8 18 25 9 2]
[2 8 18 27 8 2]
[2 8 18 28 8 2]
[2 8 18 29 8 2]
[2 8 18 30 8 2]
[2 8 18 31 8 2]
[2 8 18 32 8 2]
[2 8 18 32 9 2]
[2 8 18 32 10 2]
[2 8 18 32 11 2]
[2 8 18 32 12 2]
[2 8 18 32 13 2]
[2 8 18 32 14 2]
[2 8 18 32 15 2]
[2 8 18 32 17 1]
[2 8 18 32 18 1]
[2 8 18 32 18 2]
[2 8 18 32 18 3]
[2 8 18 32 18 4]
[2 8 18 32 18 5]
[2 8 18 32 18 6]
[2 8 18 32 18 7]
[2 8 18 32 18 8]
[2 8 18 32 18 8 1]
[2 8 18 32 18 8 2]
[2 8 18 32 18 9 2]
[2 8 18 32 18 10 2]
[2 8 18 32 20 9 2]
[2 8 18 32 21 9 2]
[2 8 18 32 22 9 2]
[2 8 18 32 24 8 2]
[2 8 18 32 25 8 2]
[2 8 18 32 25 9 2]
[2 8 18 32 27 8 2]
[2 8 18 32 28 8 2]
[2 8 18 32 29 8 2]
[2 8 18 32 30 8 2]
[2 8 18 32 31 8 2]
[2 8 18 32 32 8 2]
[2 8 18 32 32 10 1]
[2 8 18 32 32 10 2]
[2 8 18 32 32 11 2]
[2 8 18 32 32 12 2]
[2 8 18 32 32 13 2]
[2 8 18 32 32 14 2]
[2 8 18 32 32 15 2]
[2 8 18 32 32 16 2]
[2 8 18 32 32 18 1]
[2 8 18 32 32 18 2]
[2 8 18 32 32 18 3]
[2 8 18 32 32 18 4]
[2 8 18 32 32 18 5]
[2 8 18 32 32 18 6]
[2 8 18 32 32 18 7]
[2 8 18 32 32 18 8]

```
> 14 votes

# Answer
## GolfScript (96 bytes)

Output is in the form

```
[2 8 18 18]

```

This uses a magic string which contains non-printable characters, so I'm giving the script in xxd format:

```
0000000: 7e30 5c27 0193 ca05 528e 6b25 e461 4d12  ~0\'....R.k%.aM.
0000010: 3195 9abf c9a4 bfad 588b d876 5e72 c82a  1.......X..v^r.*
0000020: 2dd3 6e92 4940 e00b 80dc 71f6 fc97 2732  -.n.I@....q...'2
0000030: 3536 6261 7365 2037 6261 7365 3c7b 2731  56base 7base<{'1
0000040: 0a29 0a5c 295c 0a2b 310a 2b29 0a40 2940  .).\)\.+1.+).@)@
0000050: 400a 402b 5c28 3227 6e2f 3d7e 7d2f 5d60  @.@+\(2'n/=~}/]`

```

For online testing I'm writing the magic string with escapes:

```
"\x01\x93\xCA\x05R\x8Ek%\xE4aM\x121\x95\x9A\xBF\xC9\xA4\xBF\xADX\x8B\xD8v^r\xC8*-\xD3n\x92I@\xE0\v\x80\xDCq\xF6\xFC\x97"

```

but it's equivalent when you're not running into problems of pasting characters into browser textareas.

The approach is to build a virtual machine with 7 instructions, each of which manipulates a list of electron counts. Then for element `n` we start with an electron count list of `0` and run the first `n` instructions from the list encoded by the magic string.

The instructions are:

1. Add a new shell with 1 electron: `1`
2. Add an electron to the outer shell: `)`
3. Add an electron to the next-to-outer shell: `\)\`
4. Combine the two outer shells and add one electron: `+)`. (This is used only for palladium).
5. Combine the two outer shells and create a new shell with 1 electron: `+1`
6. Add an electron to the third shell in: `@)@@`
7. Add an electron to the third shell and move one from the second shell to the third shell. This only occurs when the outer shell has 2 electrons, so it's implemented as `@+\(2` rather than the longer `@2+@(@`
> 6 votes

# Answer
# Python 2 (46+271=327)

Code:

```
print open('f').read().decode('zip').split(';')[input()]

```

File `f`, containing the following binary garbage (these are the char codes)

```
120, 156, 101, 146, 219, 21, 195, 32, 12, 67, 87, 233, 8, 193, 188, 204, 201, 254, 123, 21, 40, 46, 146, 253, 65, 163, 171, 10, 98, 199, 188, 233, 149, 87, 62, 243, 247, 179, 158, 121, 174, 50, 87, 157, 171, 205, 213, 231, 210, 181, 118, 66, 119, 70, 119, 74, 119, 78, 119, 82, 119, 86, 127, 233, 147, 183, 29, 182, 103, 156, 103, 122, 76, 36, 19, 249, 68, 167, 56, 78, 49, 81, 77, 52, 19, 118, 110, 210, 235, 100, 19, 197, 68, 53, 209, 76, 116, 19, 250, 23, 247, 36, 56, 107, 192, 139, 30, 208, 114, 211, 183, 96, 172, 121, 87, 123, 253, 6, 90, 175, 66, 23, 118, 66, 15, 216, 6, 118, 130, 205, 96, 63, 216, 18, 119, 197, 141, 185, 222, 6, 146, 36, 76, 138, 16, 101, 162, 66, 84, 29, 225, 153, 157, 254, 163, 90, 100, 32, 229, 135, 136, 106, 201, 226, 104, 16, 225, 136, 22, 38, 70, 97, 204, 140, 133, 177, 50, 246, 251, 33, 23, 170, 71, 97, 204, 140, 133, 177, 50, 54, 198, 206, 168, 14, 253, 155, 195, 187, 135, 55, 220, 103, 145, 199, 69, 230, 188, 157, 225, 63, 44, 207, 121, 25, 53, 26, 110, 75, 247, 9, 95, 170, 27, 187, 248, 201, 75, 28, 126, 152, 255, 111, 232, 41, 56, 62, 147, 130, 35, 193, 201, 193, 41, 193, 169, 193, 105, 193, 209, 80, 79, 172, 153, 111, 72, 188, 36, 241, 158, 196, 171, 18, 111, 203, 185, 16, 95, 151, 67, 8, 97

```

Base64:

```
eJxlktsVwyAMQ1fpCMG8zMn+exUoLpL9QaOrCmLHvOmVVz7z97Oeea4yV52rzdXn0rV2QndGd0p3
TndSd1Z/6ZO3HbZnnGd6TCQT+USnOE4xUU00E3Zu0utkE8VENdFMdBP6F/ckOGvAix7QctO3YKx5
V3v9BlqvQhd2Qg/YBnaCzWA/2BJ3xY253gaSJEyKEGWiQlQd4Zmd/qNaZCDlh4hqyeJoEOGIFiZG
YcyMhbEy9vshF6pHYcyMhbEyNsbOqA79m8O7hzfcZ5HHRea8neE/LM95GTUabkv3CV+qG7v4yUsc
fpj/b+gpOD6TgiPBycEpwanBacHRUE+smW9IvCTxnsSrEm/LuRBfl0MIYQ==

```

On request, this is now a full program rather than a function.

Old answer: Python (Naive baseline, 422):

```
f=lambda n:'eJxlktsVwyAMQ1fpCMG8zMn+exUoLpL9QaOrCmLHvOmVVz7z97Oeea4yV52rzdXn0rV2QndGd0p3TndSd1Z/6ZO3HbZnnGd6TCQT+USnOE4xUU00E3Zu0utkE8VENdFMdBP6F/ckOGvAix7QctO3YKx5V3v9BlqvQhd2Qg/YBnaCzWA/2BJ3xY253gaSJEyKEGWiQlQd4Zmd/qNaZCDlh4hqyeJoEOGIFiZGYcyMhbEy9vshF6pHYcyMhbEyNsbOqA79m8O7hzfcZ5HHRea8neE/LM95GTUabkv3CV+qG7v4yUscfpj/b+gpOD6TgiPBycEpwanBacHRUE+smW9IvCTxnsSrEm/LuRBfl0MIYQ=='.decode('base64').decode('zip').split(';')[n]

```

Contents of the zip:

```
>>>'eJxlktsVwyAMQ1fpCMG8zMn+exUoLpL9QaOrCmLHvOmVVz7z97Oeea4yV52rzdXn0rV2QndGd0p3TndSd1Z/6ZO3HbZnnGd6TCQT+USnOE4xUU00E3Zu0utkE8VENdFMdBP6F/ckOGvAix7QctO3YKx5V3v9BlqvQhd2Qg/YBnaCzWA/2BJ3xY253gaSJEyKEGWiQlQd4Zmd/qNaZCDlh4hqyeJoEOGIFiZGYcyMhbEy9vshF6pHYcyMhbEyNsbOqA79m8O7hzfcZ5HHRea8neE/LM95GTUabkv3CV+qG7v4yUscfpj/b+gpOD6TgiPBycEpwanBacHRUE+smW9IvCTxnsSrEm/LuRBfl0MIYQ=='.decode('base64').decode('zip')
';1;2;2 1;2 2;2 3;2 4;2 5;2 6;2 7;2 8;2 8 1;2 8 2;2 8 3;2 8 4;2 8 5;2 8 6;2 8 7;2 8 8;2 8 8 1;2 8 8 2;2 8 9 2;2 8 10 2;2 8 11 2;2 8 13 1;2 8 13 2;2 8 14 2;2 8 15 2;2 8 16 2;2 8 18 1;2 8 18 2;2 8 18 3;2 8 18 4;2 8 18 5;2 8 18 6;2 8 18 7;2 8 18 8;2 8 18 8 1;2 8 18 8 2;2 8 18 9 2;2 8 18 10 2;2 8 18 12 1;2 8 18 13 1;2 8 18 13 2;2 8 18 15 1;2 8 18 16 1;2 8 18 18;2 8 18 18 1;2 8 18 18 2;2 8 18 18 3;2 8 18 18 4;2 8 18 18 5;2 8 18 18 6;2 8 18 18 7;2 8 18 18 8;2 8 18 18 8 1;2 8 18 18 8 2;2 8 18 18 9 2;2 8 18 19 9 2;2 8 18 21 8 2;2 8 18 22 8 2;2 8 18 23 8 2;2 8 18 24 8 2;2 8 18 25 8 2;2 8 18 25 9 2;2 8 18 27 8 2;2 8 18 28 8 2;2 8 18 29 8 2;2 8 18 30 8 2;2 8 18 31 8 2;2 8 18 32 8 2;2 8 18 32 9 2;2 8 18 32 10 2;2 8 18 32 11 2;2 8 18 32 12 2;2 8 18 32 13 2;2 8 18 32 14 2;2 8 18 32 15 2;2 8 18 32 17 1;2 8 18 32 18 1;2 8 18 32 18 2;2 8 18 32 18 3;2 8 18 32 18 4;2 8 18 32 18 5;2 8 18 32 18 6;2 8 18 32 18 7;2 8 18 32 18 8;2 8 18 32 18 8 1;2 8 18 32 18 8 2;2 8 18 32 18 9 2;2 8 18 32 18 10 2;2 8 18 32 20 9 2;2 8 18 32 21 9 2;2 8 18 32 22 9 2;2 8 18 32 24 8 2;2 8 18 32 25 8 2;2 8 18 32 25 9 2;2 8 18 32 27 8 2;2 8 18 32 28 8 2;2 8 18 32 29 8 2;2 8 18 32 30 8 2;2 8 18 32 31 8 2;2 8 18 32 32 8 2;2 8 18 32 32 10 1;2 8 18 32 32 10 2;2 8 18 32 32 11 2;2 8 18 32 32 12 2;2 8 18 32 32 13 2;2 8 18 32 32 14 2;2 8 18 32 32 15 2;2 8 18 32 32 16 2;2 8 18 32 32 18 1;2 8 18 32 32 18 2;2 8 18 32 32 18 3;2 8 18 32 32 18 4;2 8 18 32 32 18 5;2 8 18 32 32 18 6;2 8 18 32 32 18 7;2 8 18 32 32 18 8'
>>>len(_)
1478

```

And a quick test:

```
map(f, range(119))
Out[48]:
['',
 '1',
 '2',
 '2 1',
 '2 2',
 '2 3',
 '2 4',
 '2 5',
 '2 6',
 '2 7',
 '2 8',
 '2 8 1',
 '2 8 2',
 '2 8 3',
 '2 8 4',
 '2 8 5',
 '2 8 6',
 '2 8 7',
 '2 8 8',
 '2 8 8 1',
 '2 8 8 2',
 '2 8 9 2',
 '2 8 10 2',
 '2 8 11 2',
 '2 8 13 1',
 '2 8 13 2',
 '2 8 14 2',
 '2 8 15 2',
 '2 8 16 2',
 '2 8 18 1',
 '2 8 18 2',
 '2 8 18 3',
 '2 8 18 4',
 '2 8 18 5',
 '2 8 18 6',
 '2 8 18 7',
 '2 8 18 8',
 '2 8 18 8 1',
 '2 8 18 8 2',
 '2 8 18 9 2',
 '2 8 18 10 2',
 '2 8 18 12 1',
 '2 8 18 13 1',
 '2 8 18 13 2',
 '2 8 18 15 1',
 '2 8 18 16 1',
 '2 8 18 18',
 '2 8 18 18 1',
 '2 8 18 18 2',
 '2 8 18 18 3',
 '2 8 18 18 4',
 '2 8 18 18 5',
 '2 8 18 18 6',
 '2 8 18 18 7',
 '2 8 18 18 8',
 '2 8 18 18 8 1',
 '2 8 18 18 8 2',
 '2 8 18 18 9 2',
 '2 8 18 19 9 2',
 '2 8 18 21 8 2',
 '2 8 18 22 8 2',
 '2 8 18 23 8 2',
 '2 8 18 24 8 2',
 '2 8 18 25 8 2',
 '2 8 18 25 9 2',
 '2 8 18 27 8 2',
 '2 8 18 28 8 2',
 '2 8 18 29 8 2',
 '2 8 18 30 8 2',
 '2 8 18 31 8 2',
 '2 8 18 32 8 2',
 '2 8 18 32 9 2',
 '2 8 18 32 10 2',
 '2 8 18 32 11 2',
 '2 8 18 32 12 2',
 '2 8 18 32 13 2',
 '2 8 18 32 14 2',
 '2 8 18 32 15 2',
 '2 8 18 32 17 1',
 '2 8 18 32 18 1',
 '2 8 18 32 18 2',
 '2 8 18 32 18 3',
 '2 8 18 32 18 4',
 '2 8 18 32 18 5',
 '2 8 18 32 18 6',
 '2 8 18 32 18 7',
 '2 8 18 32 18 8',
 '2 8 18 32 18 8 1',
 '2 8 18 32 18 8 2',
 '2 8 18 32 18 9 2',
 '2 8 18 32 18 10 2',
 '2 8 18 32 20 9 2',
 '2 8 18 32 21 9 2',
 '2 8 18 32 22 9 2',
 '2 8 18 32 24 8 2',
 '2 8 18 32 25 8 2',
 '2 8 18 32 25 9 2',
 '2 8 18 32 27 8 2',
 '2 8 18 32 28 8 2',
 '2 8 18 32 29 8 2',
 '2 8 18 32 30 8 2',
 '2 8 18 32 31 8 2',
 '2 8 18 32 32 8 2',
 '2 8 18 32 32 10 1',
 '2 8 18 32 32 10 2',
 '2 8 18 32 32 11 2',
 '2 8 18 32 32 12 2',
 '2 8 18 32 32 13 2',
 '2 8 18 32 32 14 2',
 '2 8 18 32 32 15 2',
 '2 8 18 32 32 16 2',
 '2 8 18 32 32 18 1',
 '2 8 18 32 32 18 2',
 '2 8 18 32 32 18 3',
 '2 8 18 32 32 18 4',
 '2 8 18 32 32 18 5',
 '2 8 18 32 32 18 6',
 '2 8 18 32 32 18 7',
 '2 8 18 32 32 18 8']

```
> 5 votes

# Answer
# MATLAB - ~~248~~ ~~244~~ ~~241~~ 178 + 44 = 222 bytes

Minified:

```
i=1;a=fread(fopen('a'));b=fix(a/7);a=a-7*b+1;d=0*a;for n=1:input(''),A=a(i);if b(i),m=1;i=i+(d(A)+2>b(i));else A=A-[1;0];m=[2;-1];i=i+1;end;d(A)=d(A)+m;end;fprintf('%d ',d(~~d));

```

Expanded:

```
i = 1;
a = fread( fopen( 'a' ) );
b = fix( a/7 );
a = a-7*b+1;
d = 0*a;
for n = 1:input('')
    A = a(i);
    if b(i)
        m = 1;
        i = i + (d(A)+2 > b(i));
    else
        A = A - [1; 0];
        m = [2; -1];
        i = i + 1;
    end
    d(A) = d(A) + m;
end
fprintf( '%d ', d(~~d) );

```

Binary File Dependency (Filename '*a*'):

```
0e 39 3a 11  4f 03 72 03  3b 12 49 04  5e 12 04 73
04 3c 13 43  88 04 b2 43  04 e3 6d 05  82 3d 14 4b
05 9e 05 b3  44 05 e4 06  14 75 06 3e

```

I trust this is a "complete program" in that it can be invoked from the commandline, it reads from `stdin` and outputs to `stdout`.

It uses a kind of two-instruction bytecode to build the electron configurations. The two instructions are

```
inc D until N      (i.e. increment valence D by 1; advance to next instruction when D = N)

```

and

```
pulldown D         (i.e. pull down one electron from valence D, thereby decrementing it by 1
                         and incrementing valence D-1 by 2)

```

The instructions are encoded in two arrays. The first stores the `D` argument in all cases. The second stores the `N` argument or `0` to indicate a `pulldown` instruction, since `N = 0` is never used as an argument.

The complete sequence of instructions is:

```
inc 1 until 2
inc 2 until 8
inc 3 until 8
inc 4 until 2
inc 3 until 11
pulldown 4

inc 3 until 16
pulldown 4

inc 4 until 8
inc 5 until 2
inc 4 until 10
pulldown 5

inc 4 until 13
inc 5 until 2
pulldown 5

inc 4 until 16
pulldown 5

inc 5 until 8
inc 6 until 2
inc 5 until 9
inc 4 until 19
pulldown 5

inc 4 until 25
inc 5 until 9
pulldown 5

inc 4 until 32
inc 5 until 15
pulldown 6

inc 5 until 18
inc 6 until 8
inc 7 until 2
inc 6 until 10
pulldown 6

inc 5 until 22
pulldown 6

inc 5 until 25
inc 6 until 9
pulldown 6

inc 5 until 32
pulldown 7

inc 7 until 2
inc 6 until 16
pulldown 7

inc 7 until 8

```

~~It's worth noting that 28 characters can be dropped if we use the MATLAB-specific character set, but I wanted my solution to be representable as plaintext on Stack Exchange, without any external file references.~~

External file references it is.

### Sample Outputs

`39`: `2 8 18 9 2`

`78`: `2 8 18 32 17 1`

`117`: `2 8 18 32 32 18 7`

`5`: `2 3`
> 3 votes

# Answer
# CJam, ~~309~~ 289 bytes

```
0000000: 22 cc b5 a3 1a f7 bd 07 1b 26 ce 73 16 55 87 08  "........&.s.U..
0000010: 27 d2 65 54 66 ac c1 38 ff de 95 d8 8a 77 6d 4e  '.eTf..8.....wmN
0000020: 0d 13 df bb b7 c6 8c ae 6b 32 4d b9 f1 7c b9 f1  ........k2M..|..
0000030: bc 68 2d 8a 5c 22 e6 5c 22 e1 d7 c9 80 ba a5 5d  .h-.\".\"......]
0000040: 64 24 47 0b aa 78 c9 13 a5 0a 65 41 08 f3 ee e3  d$G..x....eA....
0000050: 2e 58 92 19 5f 1a 80 fc d9 30 3b 51 99 c7 1b 51  .X.._....0;Q...Q
0000060: ba 0c 8a 3c 7d f0 60 1e d5 1c e7 2f 33 16 c8 1f  ...<}.`..../3...
0000070: e6 df 24 75 d1 51 e6 af 38 b4 f7 b1 63 77 14 8d  ..$u.Q..8...cw..
0000080: d3 69 bc 99 9e a5 98 56 53 e7 71 f7 48 76 7a 24  .i.....VS.q.Hvz$
0000090: a7 dc 5c 22 fc a6 55 05 30 e2 03 d6 a8 ef 1a 9f  ..\"..U.0.......
00000a0: e4 03 c6 a0 5e 60 be 01 2b ca 12 83 d4 64 69 3d  ....^`..+....di=
00000b0: a7 2e cc 59 5e 0c bb 69 b0 19 1d e1 f2 53 e4 1b  ...Y^..i.....S..
00000c0: 6e 6d cc 45 d3 1f cc 3c b7 1b 5f ca c8 d0 94 fe  nm.E...<.._.....
00000d0: 05 ea ae dc 98 9e 9a 47 a6 fa 3a 0e c3 45 ef 31  .......G..:..E.1
00000e0: 61 a0 7c 80 55 9a 5d 7a af 8e 51 e8 5c 79 c4 22  a.|.U.]z..Q.\y."
00000f0: 32 35 36 62 33 38 62 22 24 12 23 20 5c 22 12 21  256b38b"$.# \".!
0000100: 08 00 02 22 3a 69 32 2f 7b 5f 30 3d 5f 29 33 33  ...":i2/{_0=_)33
0000110: 3f 61 40 5c 2f 5c 2a 7d 2f 30 61 2f 6c 69 28 3d  ?a@\/\*}/0a/li(=
0000120: 60                                               <

```

Works by replacing common runs (e.g., `2 8 18 32`) with integers greater than 32 and considering the array of all configurations a base 38 number, which is encoded in binary.

### Example run

```
$ base64 -d > electrons.cjam <<< Isy1oxr3vQcbJs5zFlWHCCfSZVRmrME4/96V2Ip3bU4NE9+7t8aMrmsyTbnxfLnxvGgtilwi5lwi4dfJgLqlXWQkRwuqeMkTpQplQQjz7uMuWJIZXxqA/NkwO1GZxxtRugyKPH3wYB7VHOcvMxbIH+bfJHXRUeavOLT3sWN3FI3TabyZnqWYVlPncfdIdnokp9xcIvymVQUw4gPWqO8an+QDxqBeYL4BK8oSg9RkaT2nLsxZXgy7abAZHeHyU+Qbbm3MRdMfzDy3G1/KyNCU/gXqrtyYnppHpvo6DsNF7zFhoHyAVZpdeq+OUehcecQiMjU2YjM4YiIkEiMgXCISIQgAAiI6aTIve18wPV8pMzM/YUBcL1wqfS8wYS9saSg9YA==
$ cksum electrons.cjam
3109698089 289 electrons.cjam
$ LANG=en_US cjam electrons.cjam <<< 42; echo
[2 8 18 13 1]
$ for i in {1..118}; do LANG=en_US cjam electrons.cjam <<< $i; echo; done | md5sum
d09cb34c282ee52c2466a6b80aa30d22  -

```
> 2 votes

# Answer
# Perl 5, 235 (234 + 1 for -E)

Golfed:

```
@a=unpack'C*','ABR3S4sT5tU6';if(($-=<>)~~[unpack'C*',')*,-./9:@NOYZ[\]`g']){$.+=($-~~[46,90]);$p=2+$-/33;$->87|$-~~[57..64]&&($.*=-1);$o[$p]+=$.,$o[$p+1]-=$.}$%=($%=$a[$q]/8)>$-?$-:$%,$o[$a[$q++]&7]+=$%while($--=$%);$,=$";say@o

```

Note: a hex dump is provided at the bottom of this post, as some of the string literals contain control characters (which were entered through a hex editor).

Ungolfed with comments:

```
$_=<>;
# For each byte, the first 5 bits are the number of spaces to fill at a time, the next 3 bits represent the shell number, minus 1.
# Values: 10 41 42 13 52 33 14 53 34 15 73 54 35 16 74 55 36
# The 1st shell takes 2 electrons
# Then the 2nd shell take 8, then the third takes 8...
@a=unpack'C*','ABR3S4sT5tU6';
# Contains the atomic numbers of abnormal elements
# Values: 18 1d 29 2a 2c 2d 2e 2f 39 3a 40 4e 4f 59 5a 5b 5c 5d 60 67
@b=unpack'C*',')*,-./9:@NOYZ[\]`g';
# if abnormal
if($_~~@b){
    # All abnormals, except element 46 and 90, only displace 1 electron
    $y=1+($_~~[46,90]);
    # Abnormals with atomic number less than 33 involve switches between shells 3 and 4
    # 33-65: 4 and 5
    # 66-98: 5 and 6
    # 99+ : 6 and 7
    $p = (3 + ~~($_/33)) - 1;
    # abnormals in these ranges move electrons from lower to higher
    # abnormals elsewhere do higher to lower
    if($_ >= 88 || $_ ~~ [57..64]){
        $y *= -1;
    }
    # move electrons
    $o[$p] += $y;
    $o[$p+1] -= $y;
}

    # extract max number of electrons to fill shell with
    # >> 3 is equivalent to /8 for integers; $% is always an integer.
    $% = $a[$q] / 8,
    # do not overfill
    $% = $% > $_ ? $_ : $%,
    # add electrons to shell
    $o[ $a[$q++] & 7 ] += $%
# reduce number of electrons left to fill shells with
while($_ -= $%);
# set list separator to space
$, = $";
# print list representing shells
say @o

```

Hex Dump:

```
0000000: 4061 3d75 6e70 6163 6b27 432a 272c 2710  @a=unpack'C*','.
0000010: 4142 1352 3314 5334 1573 5435 1674 5536  AB.R3.S4.sT5.tU6
0000020: 273b 6966 2828 242d 3d3c 3e29 7e7e 5b75  ';if(($-=<>)~~[u
0000030: 6e70 6163 6b27 432a 272c 2718 1d29 2a2c  npack'C*','..)*,
0000040: 2d2e 2f39 3a40 4e4f 595a 5b5c 5d60 6727  -./9:@NOYZ[\]`g'
0000050: 5d29 7b24 2e2b 3d28 242d 7e7e 5b34 362c  ]){$.+=($-~~[46,
0000060: 3930 5d29 3b24 703d 322b 242d 2f33 333b  90]);$p=2+$-/33;
0000070: 242d 3e38 377c 242d 7e7e 5b35 372e 2e36  $->87|$-~~[57..6
0000080: 345d 2626 2824 2e2a 3d2d 3129 3b24 6f5b  4]&&($.*=-1);$o[
0000090: 2470 5d2b 3d24 2e2c 246f 5b24 702b 315d  $p]+=$.,$o[$p+1]
00000a0: 2d3d 242e 7d24 253d 2824 253d 2461 5b24  -=$.}$%=($%=$a[$
00000b0: 715d 2f38 293e 242d 3f24 2d3a 2425 2c24  q]/8)>$-?$-:$%,$
00000c0: 6f5b 2461 5b24 712b 2b5d 2637 5d2b 3d24  o[$a[$q++]&7]+=$
00000d0: 2577 6869 6c65 2824 2d2d 3d24 2529 3b24  %while($--=$%);$
00000e0: 2c3d 2422 3b73 6179 406f                 ,=$";say@o

```
> 2 votes

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


title: Find the Chromatic Number

text:
# Question
Title: Find the Chromatic Number
Surprisingly, we haven't had any challenges on graph colouring yet!

Given an undirected graph, we can give each vertex a colour such that no two adjacent vertices share the same colour. The smallest number *χ* of distinct colours necessary to achieve this is called the *chromatic number* of the graph.

For example, the following shows a valid colouring using the minimum number of colours:

<sub>(Found on Wikipedia)</sub>

So this graph's chromatic number is *χ = 3*.

Write a program or function which, given a number of vertices *N \< 16* (which are numbered from *1* to *N*) and a list of edges, determines a graph's chromatic number.

You may receive the input and produce the output in any convenient format, as long as the input is not pre-processed. That is, you can use a string or an array, add convenient delimiters to the string or use a nested array, but whatever you do, the flattened structure should contain the same numbers as the examples below (in the same order).

You may not use built-in graph-theory related functions (like Mathematica's `ChromaticNumber`).

You may assume that the graph has no loop (an edge connecting a vertex with itself) as that would make the graph uncolourable.

This is code golf, the shortest answer (in bytes) wins.

## Examples

Your program must at least solve all of these in a reasonable amount of time. (It must solve all inputs correctly, but it may take longer for larger inputs.)

To shorten the post, in the following examples, I present the edges in a single comma-separated list. You may instead use line breaks or expect the input in some convenient array format, if you prefer.

**Triangle** (χ = 3)

```
3
1 2, 2 3, 1 3

```

**"Ring" of 6 vertices** (χ = 2)

```
6
1 2, 2 3, 3 4, 4 5, 5 6, 6 1

```

**"Ring" of 5 vertices** (χ = 3)

```
5
1 2, 2 3, 3 4, 4 5, 5 1

```

**Example picture above** (χ = 3)

```
6
1 2, 2 3, 3 4, 4 5, 5 6, 6 1, 1 3, 2 4, 3 5, 4 6, 5 1, 6 2

```

**Generalisation of the above for 7 vertices** (χ = 4)

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

```

**Petersen graph** (χ = 3)

```
10
1 2, 2 3, 3 4, 4 5, 5 1, 1 6, 2 7, 3 8, 4 9, 5 10, 6 8, 7 9, 8 10, 9 6, 10 7

```

**Complete graph of 5 vertices, plus disconnected vertex** (χ = 5)

```
6
1 2, 1 3, 1 4, 1 5, 2 3, 2 4, 2 5, 3 4, 3 5, 4 5

```

**Complete graph of 8 vertices** (χ = 8)

```
8
1 2, 1 3, 1 4, 1 5, 1 6, 1 7, 1 8, 2 3, 2 4, 2 5, 2 6, 2 7, 2 8, 3 4, 3 5, 3 6, 3 7, 3 8, 4 5, 4 6, 4 7, 4 8, 5 6, 5 7, 5 8, 6 7, 6 8, 7 8

```

**Triangular lattice with 15 vertices** (χ = 3)

```
15
1 2, 1 3, 2 3, 2 4, 2 5, 3 5, 3 6, 4 5, 5 6, 4 7, 4 8, 5 8, 5 9, 6 9, 6 10, 7 8, 8 9, 9 10, 7 11, 7 12, 8 12, 8 13, 9 13, 9 14, 10 14, 10 15, 11 12, 12 13, 13 14, 14 15

```

# Answer
# Python 2.7 - ~~122~~ ~~109~~ ~~111~~ ~~109~~ ~~108~~ 103

```
f=lambda n,e,m=1:any(all(t*m//m**a%m!=t*m//m**b%m for(a,b)in e)for t in range(m**n))and m or f(n,e,m+1)

```

Usage:

```
print f(5, [(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)])

```

Brute force by increasing the chromatic number (m) and check all possible colorings. One coloring can be described as a number in base m. So the possible colorings are 0, 1, ..., m^n-1.

edit: The complete graph of 8 vertices takes quite long. But my laptop solves it in about 10 minutes. The other test cases take only a few seconds.

---

edit 2: Read that preprocessing is allowed, so I let the index of the vertices start with 0: shortens t\*m//m\**x%m to t//m\**a%m (-2). Dissolve lambda and put m into function params (-11)

---

edit 3: preprocessing is **not** allowed -\> back to t\*m (+4), simplified // to / (-2).

---

edit 4: remove square brackets in any (-2), thanks xnor.

---

edit 5: instead of taking modulo m twice, simply subtract them and afterwards use modulo (-1). This is also quite a performance improvement. All testcases together take about 25 seconds on my laptop.

---

edit 6: recursive call instead of while 1: and m+=1 (-5). Thanks again, xnor.
> 4 votes

# Answer
# Java - ~~241~~ 218

```
int k,j,c;int f(int n,int[]e){for(k=1;k<=n;k++)for(long p=0;p<x(n);p++){for(j=0,c=0;j<e.length;c=p%x(e[j])/x(e[j]-1)==p%x(e[j+1])/x(e[j+1]-1)?1:c,j+=2);if(c<1)return k;}return 0;}int x(int a){return(int)Math.pow(k,a);}

```

The most obvious way to do this given the constraints is brute force. Just step through each chromatic number `k`, and assign each color to each vertex. If no neighbors are the same color, you have your number. If not, move along.

This takes longest for the test case for `χ = 8` (complete graphs suck here), but it's still under 15 seconds (ok, about 100s with latest edit).

Input is the number of vertices `n`, and an array of edge vertices `e[]` given in the same order as the OPs comma separated values.

With line breaks:

```
int k,j,c;
int f(int n,int[]e){
    for(k=1;k<=n;k++)
        for(long p=0;p<x(n);p++){
            for(j=0,c=0;
                j<e.length;
                c=p%x(e[j])/x(e[j]-1)==p%x(e[j+1])/x(e[j+1]-1)?1:c,
                j+=2);
            if(c<1)return k;
        }
    return 0;
}
int x(int a){return(int)Math.pow(k,a);}

```

Oh, and this assumes the input is some sort of colorable graph. If an edge loops from v1 to v1, or there are no vertices, it can't be colored and will output 0. It will still work for graphs with no edges `χ=1`, etc.
> 2 votes

# Answer
# Python 3 - 162

Uses the same brute-force approach, but uses the itertools library for hopefully faster combination generation. Solves the complete 8-graph in \< 1 min on my fairly ordinary machine.

```
import itertools as I
def c(n,v):
 for i in range(1,n+1):
  for p in I.product(range(i),repeat=n):
   if(0==len([x for x in v if(p[x[0]]==p[x[1]])])):return i

```

Example usage for the complete 8-graph case:

```
print(c(8,[x for x in I.combinations(range(8), 2)]))

```
> 2 votes

# Answer
# Haskell, 163 bytes

```
p x=f(length x)(transpose x)1
f a[b,c]d|or$map(\x->and$g x(h b)(h c))(sequence$replicate a[1..d])=d|0<1=f a b c(d+1)
g a=zipWith(\x y->a!!x/=a!!y)
h=map(flip(-)1)

```

Usage would be like this:

```
p [[1, 2],[2, 3],[3, 1]]

```

Basic brute force approach. Check all the possible coloring combinations if they are valid. Not much else to say here except that I am happy to hear any tips for shortening this even further ;)
> 1 votes

---
Tags: code-golf, graph-theory
---


title: Integer Emotions

text:
# Question
Title: Integer Emotions
Write a program or function that "reacts" to a given integer *n* (input via function parameter/args/stdin)

The program doesn't care about negative numbers, likes even, dislikes odd numbers and fears the number 13.

It should output the following:

**if n\<0:**

```
 --------------------------
 |                        |
 |                        |
(|      _          _      |)
 |                        |
 |                        |
 |                        |
 |                        |
 |       oooooooooo       |
 |                        |
 |                        |
 |                        |
 --------------------------

```

**if n%2 == 0 and n\>-1:**

```
 --------------------------
 |                        |
 |                        |
(|      ^          ^      |)
 |                        |
 |                        |
 |                        |
 |     o            o     |
 |       oooooooooo       |
 |                        |
 |                        |
 |                        |
 --------------------------

```

**if n%2 == 1 and n\>-1 and n!=13:**

```
 --------------------------
 |                        |
 |                        |
(|      >          <      |)
 |                        |
 |                        |
 |                        |
 |                        |
 |       oooooooooo       |
 |     o            o     |
 |                        |
 |                        |
 --------------------------

```

**if n==13:**

```
 --------------------------
 |                        |
 |                        |
(|     (O)        (O)     |)
 |                        |
 |                        |
 |       oooooooooo       |
 |       o        o       |
 |       oooooooooo       |
 |                        |
 |                        |
 |                        |
 --------------------------

```

The shortest solution in bytes wins.

# Answer
> 4 votes
# CJam - 169

```
S24*aB*2li_D=3{_0<2{_2%}?}?\;:X"^^<>__":s"(O)"a2*+2/=~6X3=-{S*_@+_,C\-S*2*+@@++}:F~t7'o5*_7F:MtX3={5Mt6'o_7Ft}*X2<{X2*6+'o_5Ft}*{" |"\+'|+}%S'-26*+aa2*\*_3=1>"()"\*3\tN*

```

Try it at http://cjam.aditsu.net/

High-level explanation:

`S24*aB*` makes a matrix full of spaces, for the face without the edges
`li_D=3{_0<2{_2%}?}?\;:X` reads the number and converts it to 0 (even), 1 (odd), 2 (negative) or 3 (13), storing it in X
`X"^^<>__":s"(O)"a2*+2/=~` selects the eye types (2 strings)
`{S*_@+_,C\-S*2*+@@++}:F` \- function F takes 2 strings (say S1, S2) and a number (say N) and makes a 24-char string containing N spaces, S2, other spaces, S1, N spaces
`2 (eyes) 6X3=- (F)~t` puts the eyes line in the matrix
`7'o5*_7F:Mt` puts the common mouth line in the matrix, and also saves it in M
`X3={5Mt6'o_7Ft}*` if X is 3, it puts M again in the matrix, 2 lines higher, and puts the mouth sides in between
`X2<{X2*6+'o_5Ft}*` if X is 0 or 1, it puts the mouth corners in the appropriate position
`{" |"\+'|+}%` adds vertical edges and a space on the left on every line
`S'-26*+aa2*\*` adds the horizontal edges
`_3=1>"()"\*3\t` adds the ears
`N*` adds newline separators

# Answer
> 4 votes
## Ruby, ~~241~~ 224

```
f=->n{s=" #{?-*26}
"
s+=" |#{' '*24}|
"*11+s
s[84]=?(
s[110]+=?)
s[233,12]=m=?O*12
s[91,3]=s[102,3]=n<0?' _ ':n==13?(s[177,12]=m;s[205]=s[216]=?O;'(O)'):(s[203+d=n%2*56]=s[218+d]=?O;" #{n%2<1??^:b=?>} ")
s[103]=?<if b
$><<s}

```

This defines a function to be called like `f[13]`. I'm sure there's a lot of room for improvement, similar what Ventero helped me do here.

Basically, I'm building the rough framework first, and attach ears as well as the mouth. Then I place the eyes depending on the number. While working out the characters to put into the eyes, I also take care of the different mouths so I don't have to check for the type of number again. Finally I need to fix the right eye for odd numbers, because the code above puts the same string into both eyes.

# Answer
> 4 votes
# C# - 349 bytes

Certainly not going to win any awards, but a different way of doing things.

Golfed:

```
class P{static void Main(string[]A){int j=64,i,r=0,n=int.Parse(A[0]);for(var f=(n<0?"IDID-TDTD-":n==13?"HDHD(IDIDOJDJD)SDSD(TDTDOUDUD)KIRI JHSJo":n%2<1?"IDID^TDTD^HIHIoUIUIo":"IDID>TDTD<HKHKoUKUKo")+@"JJSJoCBZM BB[M|BA[N-ADAD(\D\D)AA\N AA]N"+"\n";j++<78;)for(i=64;i++<93;System.Console.Write(f[r]))for(r=0;f[r++]>i|f[r++]>j|i>f[r++]|j>f[r++];r++);}}

```

Less golfed:

```
class P
{
    static void Main(string[]A)
    {
        int j=64,i,r=0,n=int.Parse(A[0]); // everything is offset by 65 in this program

        for(
            var f=(n<0?"IDID-TDTD-": // this string describes a set of rectangles (x1,y1,x2,y2,ch)
                n==13?"HDHD(IDIDOJDJD)SDSD(TDTDOUDUD)KIRI JHSJo":
                n%2<1?"IDID^TDTD^HIHIoUIUIo":
                "IDID>TDTD<HKHKoUKUKo"
                )+@"JJSJoCBZM BB[M|BA[N-ADAD(\D\D)AA\N AA]N"+"\n";

            j++<78;) // the loop then prints the rectangles to the screen
            for(i=64;i++<93;System.Console.Write(f[r]))
                for(r=0;f[r++]>i|f[r++]>j|i>f[r++]|j>f[r++];r++);
    }
}

```

# Answer
> 3 votes
# Python 2 - 255

Not *really* short, but I'll post it anyway:

```
n=input()
o='o'
S='  '
w=y=7*S
b=' '+'-'*26+'\n'
p=' |%19s     |\n'
E=p%y*2
v=S+o*10+S
u=z=o+6*S+o
A=a='^ '
if n%2:A='< ';a='> ';u=y;w=z
if n<0:A=a='_ ';u=w=y
if n==13:A=a='(O)';u=w=v;v=S+o+S*4+o+S
print b+E+'(|%8s%11s     |)\n'%(a,A)+E+p%u+p%v+p%w+E+b

```

I miss item assignment for strings in Python! :( Then one could start with the character matrix and simply modify eyes and mouth.

# Answer
> 3 votes
# Python 2, 257

Not a winner, but an alternate approach, got quite close! I have hope I can squeeze a few more chars out of it. Builds all the lines piece by piece, using common substrings to really squeeze out the bytes.

```
X,Z=R=" |"
Q=X*5
Y=X*7
A=X+"-"*26
B=R+X*24+Z
n=input()
a,b,c,d,e,f,g=((("^>^<o  o "+Q)[n%2::2],"OO  ()o")[n==13],"__"+Q)[n<0]
for F in(A,B,B,"(|"+Q+e+a+f+Y+X+e+b+f+Q+"|)",B,B,R+Y+g*10+Y+Z,R+Q+c+X+g+Y+X+g+X+c+Q+Z,R+Y+"o"*10+Y+Z,R+Q+d+Y+Q+d+Q+Z,B,B,A):print F

```

# Answer
> 2 votes
# CJam, 202

```
[S'-26*N]:Z[S'|:PS24*PN]:RR'(PS5*qi:XD=X0<-X2%2*+:Y[" ^ "_" > ""(O)"" - "__]=S8*Y[" ^ ""   "" < ""(O)"" - "__]=S5*P')NRRXD=[SPS7*'oA*S7*PN]:QR?Y[[SPS5*'oSC*'oS5*PN]:T_R[SPS7*'oS8*'oS7*PN]RRR]=QY2=TR?RRZ

```

---
Tags: code-golf, ascii-art, number, kolmogorov-complexity
---