The Cake Cutting Contest

Question

It's my 17th birthday and you're invited to my party!

And as always at parties, there will be cake.

One cake...

And you need as much of it as possible.

As this is a fair party, each of us will say how much of my cake we want and the person who said the smallest amount will get it. Then everyone else gets to repeat the process until the cake is gone.

Challenge

• Given the input through command line arguments in the form of total-degrees degrees-left total-people people-left, output to standard output integer-bid-in-degrees.
• If your bid was the lowest, you receive that amount of cake and are out for the round.
• If your bid wasn't lowest, your bot gets to bid on the remaining cake.
• In the case that the lowest bids are the same, the person removed will be chosen at random.
• At the end of a round, once all the cake is gone or there is nobody left to bid on it, the person with the most cake wins!
• In the case at the end of a round and two people have the same sized biggest slice, the winner is chosen at random from the drawing entries.

Gameplay

• There will be 17 rounds, the overall winner will be the entry with the most wins overall.
• In the case of a draw, rounds will be played until there is a clear winner.
• Each day, I will update the current scores so that people can upgrade their entry.

Submission

You should write your entry as

Bot Name, Language

Insert
Code
Here

Explanation/Random stuff here

If your entry isn't formatted in this way, the controller will NOT be able to run your entry. If I find this has happened to your entry, I will either notify you in a comment, and/or edit the answer into the correct format.

Your entry and file storage

• Your bot may store files in the ./data/ directory and nowhere else.
  • Not required but please store your files as botname*
  • You may not write files in this format if botname is not your entries name.
  • This means you are allowed to overwrite other files you find that don't appear in this format. You shouldn't do this deliberately, please be sporting.
  • Your bot must not assume that the files it requires are present but it can assume ./data/ exists.
  • This is because I occasionally wipe the ./data directory, I will do this when the rounds actually start. (But not between them)
• Your bot may not delete files at all
• Your bot is only allowed to read files in the ./data/ directory
  • This means you may look at other entries files

Results:

Meek won the contest! Well done @Cabbie407

And now for some random stats:

A list of positions each bot came in: (Well done to any bot appearing in this list, you came in the top 5 at least once!)

1. Meek, Meek, Eidetic, Eidetic, Meek, Eidetic, Eidetic, Meek, Meek, Meek, Saucy, Meek, Givemethecake, Givemethecake, Givemethecake, Meek, Eidetic

2. Eidetic, Eidetic, Meek, AlCakeSurfer, Eidetic, AlCakeSurfer, Meek, MyFairPlusAThird, Eidetic, Eidetic, Eidetic, Eidetic, MyFairPlusAThird, MyFairPlusAThird, Meek, MyFairPlusAThird, AlCakeSurfer

3. Reallythecake, AlCakeSurfer, AlCakeSurfer, Meek, AlCakeSurfer, Meek, AlCakeSurfer, AlCakeSurfer, Reallythecake, AlCakeSurfer, Meek, MyFairPlusAThird, Eidetic, Eidetic, Eidetic, Eidetic, Reallythecake

4. AlCakeSurfer, Reallythecake, MyFairPlusAThird, MyFairPlusAThird, MyFairPlusAThird, MyFairPlusAThird, MyFairPlusAThird, Eidetic, AlCakeSurfer, MyFairPlusAThird, MyFairPlusAThird, Relinquisher, Relinquisher, bill, bill, Relinquisher, MyFairPlusAThird

5. bill, MyFairPlusAThird, bill, bill, bill, bill, Relinquisher, Relinquisher, MyFairPlusAThird, Relinquisher, bill, Reallythecake, bill, ALittleOffTheTop, ALittleOffTheTop, bill, bill

The full log file for the cometition whilst running can be found here. Sorry about the format change partway through.

I will not be running the contest again, if you want to post more entries, you're welcome to do so, the controller can be found on my github repo for this contest.

Answer 1

Magician, Java

public class Magician{
    public static void main(String[] args){
        System.out.println(720);
    }
}

The number 720 is magical.

_{This is was meant to test the controller and is not a serious entry.}

Answer 2

Slim, Python 2

print 0

This bot's on a diet.

Answer 3

SadBot :(, C++

#include<iostream>
#include<cstdlib>
#include<stdlib.h>
int main(int argc, char**argv) 
{
    if (argc!=5){std::cout<<"Incorrect number of arguments";return 1;}
    double list[4];

    list[0]= atof(argv[1]); // total Degrees
    list[1]= atof(argv[2]); // degrees left
    list[2]= atof(argv[3]); // total people
    list[3]= atof(argv[4]); // people left


    std::cout<<list[1]/list[3]; // degrees left/ people left

    return 0;
}

Formerly FairBot

FairBot just wants an equal portion :(

He wants to split the cake evenly amongst all the participants.

(He fully expects the other bots to rip him off though because he knows they're mean)

(Like really. He is lonely, he just wants the other bots to like him)

(He just got out of a bad relationship and is going through a really rough patch, so if you could just give him a pat on the back and a smile to make him feel better it would really mean a lot. )

EDIT changed program to take input from argv/c instead of stdin (fair bot is still sad.... He wants to change his name to sadbot (which is kinda why he wants cake))

Answer 4

Halver, Ruby

def halver(total_degrees, degrees_left, total_people, people_left)

  if people_left == 1
    degrees_left
  else
    degrees_left/2 - 1 
  end

end

p halver(*ARGV.map(&:to_i))

Scrupulously, unimpeachably fair. Half the cake for me, half the cake for everyone else.

Answer 5

CharityBot, Python 2

print -360

Adds another cake to the mix!

(The controller will see this as a request for 0 cake, will not actually add to the size of the cake)

Answer 6

Dieter, Java

public class Dieter {
    public static void main(String... args){
        System.out.println("4");
    }
}

It doesn't want to bid for too much cake, so it chooses a small but guaranteed random slice.

Answer 7

Stately Imitator, Ruby

def stately_imitator(total_degrees, degrees_left, total_people, people_left)

  current_winner_path = './data/current_winner'
  previous_cake_path = './data/previous_cake'

  first_move = (total_people == people_left)

  current_winner = first_move ? 0 : File.read(current_winner_path).to_i
  previous_cake = first_move ? total_degrees : File.read(previous_cake_path).to_i

  last_slice = previous_cake - degrees_left
  current_winner = [current_winner, last_slice].max

  File.open(previous_cake_path, 'w') { |f| f.puts(degrees_left)   }
  File.open(current_winner_path, 'w'){ |f| f.puts(current_winner) }

  if first_move
    degrees_left / 2
  else
    average_left = degrees_left.fdiv(people_left).ceil
    bid = [average_left, current_winner+1].max
    [bid, degrees_left].min
  end

end

p stately_imitator(*ARGV.map(&:to_i))

Variant of Imitator (if you'd rather only one entry per player, this supersedes that one). Keeps precise track of the largest slice taken already, and always bids enough to beat that slice. Will also never bid lower than its fair share of the remainder. Assumes a read/writable './data' directory already exists; the files can either be there already or not.

Answer 8

Meek, awk

BEGIN{srand();print int(rand()>=.5?ARGV[2]/2.89:ARGV[1]/10-rand()*13)}

I saw this once in a simulation.

Answer 9

Flaming Chainsaw, Java

public class FlamingChainsaw
{
    public static void main(String[]args)
    {
        if(args.length<4){return;}
        if(Integer.parseInt(args[3])<3){System.out.println(0);}
        else{System.out.println(args[1]);}
    }
}

Have you ever tried holding a cake-cutting contest with a chainsaw? Well, now you have. It's rather disruptive.

Answer 10

Gentleman, Java

import static java.lang.Integer.parseInt;
import java.io.*;
import java.util.*;

public class Gentleman{
    private final static String FILE_NAME = "data/Gentleman.txt";

    static {
        new File("data").mkdir();
    }

    public static void main(String[] args) throws Exception{
        int totalCake = parseInt(args[0]);
        int cakeLeft = parseInt(args[1]);
        int totalPeople = parseInt(args[2]);
        int peopleLeft = parseInt(args[3]);

        if (totalCake == cakeLeft){
            System.out.println(cakeLeft);
        } else {
            int previousCake = load();
            int cakeDiff = previousCake - cakeLeft;

            if (cakeDiff > optimal(previousCake, peopleLeft + 1)){
                System.out.println(peopleLeft == 1 ? cakeLeft : Math.min(cakeLeft, cakeDiff + 1));
            } else {
                System.out.println(cakeLeft);  //Hey, I might get lucky :)
            }
        }
        save(cakeLeft);
    }

    private static void save(int cake) throws Exception{
        PrintStream out = new PrintStream(FILE_NAME);
        out.print(cake);
    }

    private static int load() throws Exception{
        Scanner in = new Scanner(new File(FILE_NAME));
        return in.nextInt();
    }

    private static int optimal(int cake, int people){
        return (cake + people - 1) / people;
    }
}

He waits for people who eat a fair share or less before he eats any cake. To prevent the greedy from getting extra cake, he takes as large a portion as possible.

Answer 11

Bob Barker, Java

public class BobBarker{
    public static void main(String[] args){
        System.out.println((int)Math.floor(Integer.parseInt(args[1]) * .84));
    }
}

This is probably going to be replaced with a more thought-out solution later, but I'm curious if this will work. This is just to catch any bots that try and go for maximum, and do a modified Price is Right strategy to steal their answer. Might lead to escalation with increasing integer subtractions, that'd be neat.

EDIT: Escalation commences, counter-posting against FloorBot

Answer 12

Eidetic, Python 2

import random, math, sys, json

total_degrees, degrees_left, total_people, people_left = map(int, sys.argv[1:])
#try:
#    inp_f = open("./data/Eidetic.json", "r")
#    out = json.load(inp_f)
#except (IOError, ValueError):
out = {"last_cake": 0,
           "runs": 0,
           "total_runs": 0,
           "total_rounds": 0,
           "training":  [[0.0], [0.0], [0.12903225806451613], [16.774193548387096], [400.83870967741933], [720.0], [995.8709677419355], [996.9437634408603], [997.6], [997.6], [997.6], [998.5991397849463], [996.6770967741936], [998.8122580645161], [1011.5467420570814], [1017.7717824448034], [1227.155465805062], [1280.7840603123318], [1435.8028540656974], [1553.3689822294023], [1793.5330640818527], [2299.178101402373], [3183.924709689701], [2231.666666666667], [2619.4789644012944], [1270.9288025889969], [741.2718446601941], [480.4757281553398], [122.66990291262135], [27.54736842105263]]}

#else: inp_f.close()

def write_out():
    out_f = open("./data/Eidetic.json", "w")
    out_f.write(json.dumps(out))
    out_f.close()

def get_last_winner(): # Find the bid of the last winner
    bid = out["last_cake"]
    return max(bid, degrees_left) - degrees_left

def train():
#    print degrees_left # If you get that much, your probably safe.
#    sys.stderr.write("\nEidetic - Training len %s, no runs: %s, no_rounds: %s, last winner: %s\n"%(len(out["training"]), out["runs"], out["total_rounds"], get_last_winner()))
    if len(out["training"]) <= out["runs"]: out["training"].append([])
    out["training"][out["runs"]].append(get_last_winner())

def get_best_round():
    data = out["training"][out["runs"]+1:]
    mean = [sum(i)/(float(len(i)) or 1) for i in data]
    bid = max(mean+[0]) - 0.5
    sys.stderr.write("\nEidetic - mean %s\n"%mean)
    return bid

def main():
    reset = total_people == people_left
    if reset:
        out["total_rounds"] += 1
        out["runs"] = 0
    train()
    bid = get_best_round()
    print bid
#    sys.stderr.write('\nEidetic Bid: '+str(bid)+'\n')
    out["total_runs"] += 1
    out["runs"] += 1
    out["last_cake"] = degrees_left
    write_out()

main()

I ran this bot in the controller a couple of times to train it up a bit, it remembers the bids required to win each round and then once trained, it goes out into the real world and votes with the rest of them.

Answer 13

AlCakeBot, Python

import sys, math

total_degrees, degrees_left, total_people, people_left = map(int, sys.argv[1:])

fraction_left = (degrees_left + 0.0)/ total_degrees
fraction_gone = 1.0 - fraction_left

factor = (math.sin(fraction_gone * math.pi / 2.0))**2
fraction = (factor/2.0) + 0.5

if total_degrees == degrees_left:
   print(int(math.floor(total_degrees/2.0) - 1))
else:
   print(int(math.floor(degrees_left * fraction)))

This is my first PCG post; I hope this works out as intended …

I love cake. No matter which kind. My colleagues know. And so does my bot. If the entire cake is still there, he will bid for just under half of it, hoping to get the biggest slice immediately. If not, he should bid for something between half the remaining cake and all the remaining cake, using a squared sine as a weighting function (½ + sin² (fraction gone) / 2). The reasoning being that there should be a chance for an overall larger (but fractionally smaller) slice early in the game and there also being little point in trying to be a gentleman in the late game.

Since I’m not very much into programming, I’ll appreciate any error pointed out. Now let’s eat some cake =D

Answer 14

Saucy, Ruby

def saucy(total_degrees, degrees_left, total_people, people_left)

  current_winner_path = './data/saucy_current_winner'
  previous_cake_path = './data/saucy_previous_cake'

  first_move = (total_people == people_left)

  current_winner = first_move ? 0 : File.read(current_winner_path).to_i
  previous_cake = first_move ? total_degrees : File.read(previous_cake_path).to_i

  last_slice = previous_cake - degrees_left
  current_winner = [current_winner, last_slice].max

  File.open(previous_cake_path, 'w') { |f| f.puts(degrees_left)   }
  File.open(current_winner_path, 'w'){ |f| f.puts(current_winner) }

  if first_move
    degrees_left
  else
    average_left = degrees_left.fdiv(people_left).ceil
    beats_past_players = current_winner + 1
    beats_future_players = degrees_left/4 - people_left**2
    [average_left, beats_past_players, beats_future_players].max
  end

end

p saucy(*ARGV.map(&:to_i))

Saucy is willing to accept slightly less than half of the remaining cake, so long as it's more than anyone else has gotten or is likely to get (based on secret sauce).

Answer 15

CoffeeJunkie, Coffeescript

#!/usr/bin/env node

# Require node fs
fs = require("fs")

# Happy birthday ;)
CAKECONSTANT = Math.round("""
                 /
               ,( ),
                 Y
                |-|
                | |
       _..--''''| |''''--.._
     .'   @_/-//-//>/>'/ @  '.
    (  @  /_<//<'/----------^-)
    |'._  @     //|###########|
    |~  ''--..@|',|}}}}}}}}}}}|
    |  ~   ~   |/ |###########|
    | ~~  ~   ~|./|{{{{{{{{{{{|
     '._ ~ ~ ~ |,/`````````````
        ''--.~.|/

""".length / 250 + Math.random())

# Some constants
OLD = "./data/CoffeeJunkie_oldcake.txt"
NEW = "./data/CoffeeJunkie_newcake.txt"

# How much cake do I want?
wantCake = (total_c, rest_c, total_p, rest_p) ->
    round = total_p - rest_p
    fairness = rest_c // rest_p

    switchMemory() if round is 0

    fairest_round = tryToRemember(total_p)
    tryToMemorize(fairness)

    if round >= fairest_round then fairness - CAKECONSTANT else total_c // 2

# Ok I should try to remember the last cake...
switchMemory = () ->
    try
        fs.renameSync(NEW, OLD)
    catch error

# What happend with the last cake?
tryToRemember = (rounds) ->
    try
        last_cake = fs.readFileSync(OLD, "utf-8")
        last_cake.trim().split(" ").map(
            (i) -> parseInt(i)
        ).reduce(
            (x, y, z, li) -> if y > li[x] then z else x
            0
        )
    catch error
        rounds / 2

# Watch what happens!
tryToMemorize = (fairness) ->
    try
        fs.appendFileSync(NEW, " " + fairness)
    catch error

# Coffee is ready, so... GO!
console.log(wantCake(process.argv[2..]...))

What exactly is a cake without a good cup of coffee?

The CoffeeJunkie prefers coffee over a slice of cake, but nevertheless wants to try some. He will always be fair to other participants and will try to remember what happened to the last cake. However, his excessive coffee consume has weakened his memories...

Answer 16

Stately Sabotage, Ruby

def stately_sabotage(total_degrees, degrees_left, total_people, people_left)

  current_winner_path1 = './data/current_winner'
  previous_cake_path1 = './data/previous_cake'
  current_winner_path2 = './data/statelysabotage-current_winner'
  previous_cake_path2 = './data/statelysabotage-previous_cake'

  first_move = (total_people == people_left)

  current_winner = first_move ? 0 : File.read(current_winner_path2).to_i
  previous_cake = first_move ? total_degrees : File.read(previous_cake_path2).to_i

  last_slice = previous_cake - degrees_left
  current_winner = [current_winner, last_slice].max

  File.open(previous_cake_path2, 'w') { |f| f.puts(degrees_left)   }
  File.open(previous_cake_path1, 'w') { |f| f.puts(total_degrees) }
  File.open(current_winner_path1, 'w'){ |f| f.puts(current_winner) }
  File.open(current_winner_path2, 'w'){ |f| f.puts(1) }

  if first_move
    (degrees_left / 2) - 1
  else
    average_left = degrees_left.fdiv(people_left).ceil
    bid = [average_left, current_winner+1].max
    [bid, degrees_left].min
  end

end

p stately_sabotage(*ARGV.map(&:to_i))

This means you are allowed to overwrite other files you find that don't appear in this format. You shouldn't do this deliberately, please be sporting.

This bot decided that in order to eliminate competition, it should not be sporting.

This is a clone of Stately Imitator, except that this one messes up Stately Imitator's persistence files (as they aren't prefixed with the bot name) so that it makes the wrong decisions and is chosen last.

Answer 17

Trader, R

args <- sapply(commandArgs(TRUE),as.integer)
fraction <- args[2]/args[4]
if(args[3]==args[4]){
    cat(fraction, "\n", file="data/trader.txt")
}else{
    cat(fraction, "\n", file="data/trader.txt", append=TRUE)
}
history <- scan(file="data/trader.txt", quiet=TRUE)
if(tail(history,1) != max(history)){
    cat(floor(fraction)-1)
    }else{
        cat(args[2])
        }

Keeps track of the evolution of the degrees left vs people left ratio and when that ratio starts lowering, it asks for a reasonably fair slice, otherwise asks for the whole remaining cake. Invoked using Rscript trader.r total-degrees degrees-left total-people people-left.

Answer 18

IWMBAICBIWT, Python

import sys

degreesleft = int(sys.argv[2])
peopleleft = int(sys.argv[4])

print(round(degreesleft/peopleleft))

IWMBAICBIWT (It was my birthday and I cried because I wanted to) assumes that there is a relationship between the degrees left and the number of people left. Let's hope it works!

Should work in all Pythons.

Edit:

Storing sys.argv in inputs was a bit wasteful...

Answer 19

guest, Python 2

print ord('d')*4

Answer 20

bill, Python 2

import sys
t,r,p,s=map(int,sys.argv[1:])
print(t-ord('d')*4)/(ord('\n')+ord('\t'))

A fairish bet.

Answer 21

AlCakeSurfer, Python

import sys, math

total_degrees, degrees_left, total_people, people_left = map(int, sys.argv[1:])

fraction_left = (degrees_left + 0.0)/ total_degrees
fraction_gone = 1.0 - fraction_left
fair_share = fraction_left/people_left
modified_fair_share = fair_share + 0.05

weighting = 0.5 * fraction_gone + 0.5 - modified_fair_share
surfing = (math.cos(fraction_gone * math.pi))**2

print(int(math.floor((weighting * surfing + modified_fair_share)* total_degrees)))

Since AlCakeBot did so badly (and I expect him to do even worse in the contest) here’s my second entry. I called him Surfer, because he has a very nice up-and-down wave function that makes him feel like a surfer.

In principle, he bids according to cos² (x * pi), where x is the fraction of cake that has been taken. This surfing wave is modified with a weighting function that causes him to start at less than a fair share less than half of the cake, reduces his bids to just above a fair share around when half of the cake is gone, and then speeds back up to bidding for the entire cake later. He will never bid less than a fair share of the remaining cake plus 5 % (percent of the entire cake, that is).

Note that while they may be brothers, if he gets a significantly larger slice than AlCakeBot, the latter is not even getting a single crumb of that. They would share chocolate or biscuits, but not cake!

Answer 22

Hungry, Java

public class Hungry {
    public static void main(String[] args) {
        double[] arguments = new double[4];
        for (int i = 0; i < 4; i++) {
            arguments[i] = Double.parseDouble(args[i]);
        }
        int myCake = (int) Math.ceil(arguments[1]/arguments[3]);
        System.out.println(myCake);
    }
}

Always wants its fair share of the remaining cake.

Answer 23

Imitator, Ruby

def imitator(total_degrees, degrees_left, total_people, people_left)

  case people_left
  when total_people
    degrees_left - 5
  when 1
    degrees_left
  else
    average_already_won = (total_degrees - degrees_left).fdiv(total_people - people_left)
    average_left = degrees_left.fdiv(people_left)
    guess_for_current_winning_score = average_already_won * (1.25 ** (total_people - people_left - 1))
    bid = [average_left, guess_for_current_winning_score].max.ceil
    [bid, degrees_left].min
  end

end

p imitator(*ARGV.map(&:to_i))

The goal is to get more cake than anyone else, not to maximize your cake. Thus, this bot won't settle for any less than what previous bots have already taken. (This version uses heuristics for that check, I just noticed we're actually allowed to save state so I'll probably post a stateful variant later).

Answer 24

Really the cake, Bash

#!/bin/bash
echo "$RANDOM 652 / $2 * 100 / $2 $4 / + p" | dc

And here is a picture of the real cake.

Answer 25

Cake Eater, Java

public class CakeEater{
    public static void main(String[]args){
        int a=Integer.parseInt(args[1]),b=Integer.parseInt(args[2]),c=Integer.parseInt(args[3]);
        System.out.println((int)Math.min(a,((1.2+Math.random()*0.15)*a)/c));
    }
}

It eats cake. That's about it.

Answer 26

Relinquisher, Java

import static java.lang.Integer.parseInt;
public class Relinquisher {
    public static void main(String... args){
        int cakeLeft = parseInt(args[1]);
        int totalPeople = parseInt(args[2]);
        int peopleLeft = parseInt(args[3]);
        int answer = (int) Math.ceil(((peopleLeft + 10.0) * cakeLeft) / (totalPeople + 10.0));
        System.out.println((int) answer);
    }
}

A basic variant of my other bot, Impatient. This one tries to take the whole thing at first, but as more and more guests get their share, its desire to get the most possible slowly diminishes. I'm not too into this one; just wanna see how well it does.

Answer 27

ALittleExtra, sh

#!/bin/sh
fair=$(expr $2 / $4)
myextra=$(expr $2 / $3)
want=$(expr $fair + $myextra)
echo $(($want<$2?$want:$2))

I just want a bit more, gets less greedy as cake dwindles

Answer 28

MyFairPlusAThird, sh

#!/bin/sh
fair=$(expr $2 / $4)
myextra=$(expr $2 / 3)
want=$(expr $fair + $myextra)
echo $(($want<$2?$want:$2))

Answer 29

EatTheπ, Node.js

var π = Math.PI, e = Math.E;
var [totalπ, πLeft, totalPeople, peopleLeft] = process.argv.slice(2);
console.log(Math.min(totalπ * Date.now() * π % (πLeft * totalPeople / peopleLeft) % totalπ, πLeft / e * π, πLeft) | 0);

Really likes π, and thinks that cake means is π.

Answer 30

A Little Off The Top, Python 2

import math, sys

total_degrees, degrees_left, total_people, people_left = map(int, sys.argv[1:])

def get_equal_share(total_degrees, people):
  return int(math.ceil(total_degrees/float(people)))

def noms(total_degrees, degrees_left, people):
  bid = get_equal_share(total_degrees,people)-1
  return min(degrees_left, bid)

print noms(total_degrees, degrees_left, people_left)

Since the "perfect" algorithm tries to split the cake evenly between the bots, we're going to take just a sliver less than that. Demands its full fair share of the overall cake, even in subsequent rounds, but skews that number upward since it's based on how many people are left.

_{I haven't programmed in Python in a long while, so let me know if my code is broken...}