Cavern Master

[AMindForeverVoyaging]

I'm a bit surprised that nobody has posted their code for solving this one. Here is mine:

Code: Select all

#include <curl/curl.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_CYCLES 10000

struct MemoryStruct {
  char *memory;
  size_t size;
};

// global variables/player stats
struct MemoryStruct chunk; // variable which will hold the retrieved HTML
uint32_t player_level, dungeon_level, XP, no_of_cycles;
int32_t hitpoints;
char entry, weapon[50], inventory[3][30], inv[300], grid[9], movestring[10];
uint8_t no_of_items, position, stairs_pos;
bool north, east, south, west, stairs, fighting, go_downstairs, pick_up;
FILE* logfile;

static size_t WriteMemoryCallback(void *contents, size_t size, size_t nmemb, void *userp)
{
	size_t realsize = size * nmemb;
	struct MemoryStruct *mem = (struct MemoryStruct *)userp;

	mem->memory = realloc(mem->memory, mem->size + realsize + 1);
	if (mem->memory == NULL)
	{
		printf("not enough memory (realloc returned NULL)\n");
		exit(EXIT_FAILURE);
	}

	memcpy(&(mem->memory[mem->size]), contents, realsize);
	mem->size += realsize;
	mem->memory[mem->size] = 0;

	return realsize;
}

void getHTML(void)
{
	CURL *curl_handle;
	CURLcode errorcode;
	
	// free the memory before allocating anew
	if(chunk.memory)
		free(chunk.memory);
	
	chunk.memory = malloc(1);  /* will be grown as needed by the realloc above */
	chunk.size = 0;    /* no data at this point */
	curl_handle = curl_easy_init();
	char* URLstring  = "http://www.hacker.org/challenge/misc/d/cavern.php?";
	char* Userstring = "name=<user name>&spw=<submit password>";
	char Submitstring[200];
	strcpy(Submitstring, URLstring);
	strcat(Submitstring, movestring);
	strcat(Submitstring, Userstring);
	curl_easy_setopt(curl_handle, CURLOPT_URL, Submitstring);
	curl_easy_setopt(curl_handle, CURLOPT_WRITEFUNCTION, WriteMemoryCallback);
	curl_easy_setopt(curl_handle, CURLOPT_WRITEDATA, (void *)&chunk);
	curl_easy_setopt(curl_handle, CURLOPT_USERAGENT, "libcurl-agent/1.0");
	errorcode = curl_easy_perform(curl_handle);
	curl_easy_cleanup(curl_handle);
	
	if(errorcode != 0)
	{
		printf("Error while retrieving URL\n");
		free(chunk.memory);
		curl_global_cleanup();
		fclose(logfile);
		exit(-1);
	}
}

void parseHTML(void)
{	
	if(hitpoints <= 0)
	{
		printf("Character died\n");
		fprintf(logfile, "Died.\ncycles: %5d, entry: %c, dungeon lvl: %d, player lvl: %d\n", 
		        no_of_cycles, entry, dungeon_level, player_level);
		free(chunk.memory);
		curl_global_cleanup();
		fclose(logfile);
		exit(-1);
	}

	fighting = false;
	if( strstr(chunk.memory, "Attack") != NULL)
		fighting = true;
		
	if( (fighting == true) && ( strstr(chunk.memory, "Big monster") == NULL) )
	{
		printf("Boss is up!\n");
		fprintf(logfile, "Boss reached.\ncycles: %5d, entry: %c, dungeon lvl: %d, player lvl: %d\n", 
		        no_of_cycles, entry, dungeon_level, player_level);
		// to get the name
		fprintf(logfile, "\n\n%s", chunk.memory);
		free(chunk.memory);
		curl_global_cleanup();
		fclose(logfile);
		exit(0);
	}
	
	char *pch = strstr(chunk.memory, "Dungeon Level");
	pch = pch + 14;
	dungeon_level = atoi(pch);
	
	pch = strstr(chunk.memory, "<tr><td>") + 8;
	player_level = atoi(pch);
	
	pch = strstr(chunk.memory, "</td><td>") + 9;
	hitpoints = atoi(pch);
	
	pch = strstr(pch, "</td><td>") + 9;
	XP = atoi(pch);
	
	pch = strstr(pch, "</td><td>") + 9;
	strncpy(weapon, pch, 49);
	pch = strstr(weapon, "<");
	*pch = '\0';

	pick_up = false;
	if( strstr(chunk.memory, "Pick up") != NULL)
		pick_up = true;
	
	go_downstairs = false;
	if(player_level >= dungeon_level + 4)
		go_downstairs = true;
	
	north = east = south = west = stairs = false;
	if( strstr(chunk.memory, "North") != NULL) north = true;
	if( strstr(chunk.memory, "East")  != NULL) east  = true;
	if( strstr(chunk.memory, "South") != NULL) south = true;
	if( strstr(chunk.memory, "West")  != NULL) west  = true;

	     if (!north &&  east &&  south && !west) position = 0;
	else if (!north &&  east &&  south &&  west) position = 1;
	else if (!north && !east &&  south &&  west) position = 2;
	else if ( north &&  east &&  south && !west) position = 3;
	else if ( north &&  east &&  south &&  west) position = 4;
	else if ( north && !east &&  south &&  west) position = 5;
	else if ( north &&  east && !south && !west) position = 6;
	else if ( north &&  east && !south &&  west) position = 7;
	else if ( north && !east && !south &&  west) position = 8;
	
	if( strstr(chunk.memory, "Down Stairs") != NULL)
	{
		stairs_pos = position;
		stairs = true;
	}
	
	memset(grid, '.', 9);
	
	if(stairs_pos < 9)
		grid[stairs_pos] = 'S';
}

void makeDecision(void)
{
	strcpy(movestring, "");
	
	if(fighting)
	{
		strcpy(movestring, "attack=1&");
		entry = 'a';
	}
	else if (pick_up == true) // pick up stuff
	{
		strcpy(movestring, "tres=1&");
		entry = 'p';
	}
	else // move around randomly
	{
		bool dir_found = false;
		int dir;
		
		while(dir_found != true)
		{
			dir = rand() % 4;
		    if     (dir==0 && north) { dir_found = true; strcpy(movestring, "m=n&"); entry = 'n'; }
			else if(dir==1 && east)  { dir_found = true; strcpy(movestring, "m=e&"); entry = 'e'; }
			else if(dir==2 && south) { dir_found = true; strcpy(movestring, "m=s&"); entry = 's'; }
			else if(dir==3 && west)  { dir_found = true; strcpy(movestring, "m=w&"); entry = 'w'; }
		}
	}
	
	if(go_downstairs == true && stairs == true && !fighting)
	{
		go_downstairs = stairs = false;
		strcpy(movestring, "m=d&");
		entry = 'd';
	}
	
	no_of_cycles++;
	if(no_of_cycles >= MAX_CYCLES && !fighting)
		entry = 'x';
	
	printf("%4d The script sets entry to: %c\n", no_of_cycles, entry);
	
	if(entry == 'x')
		printf("Number of cycles = %d, terminating\n", no_of_cycles);
	
	fprintf(logfile, "cycles: %5d, entry: %c, dungeon lvl: %d, player lvl: %d\n", 
	        no_of_cycles, entry, dungeon_level, player_level);
	fflush (logfile);
}

int main()
{
	// initialize the variables
	entry = ' ';
	fighting      = false;
	player_level  = 0;
	dungeon_level = 0;
	hitpoints     = 1;
	no_of_items   = 0;
	no_of_cycles  = 0;
	north = east = south = west = stairs = go_downstairs = pick_up = false;
	position = 4;
	stairs_pos = 9;
	strcpy(weapon, "Standard Weapon");
	inventory[0][0] = '\0';
	inventory[1][0] = '\0';
	inventory[2][0] = '\0';
	movestring[0]   = '\0';
	
	logfile = fopen("logfile.txt", "w");
	srand(time(NULL));
	curl_global_init(CURL_GLOBAL_ALL);
	
	// main loop
	while(entry != 'x')
	{
		getHTML();
		parseHTML();
		makeDecision();
	}
	
	fclose(logfile);
	free(chunk.memory);
	curl_global_cleanup();
	return 0;
}

[DaymItzJack]

Nobody probably posted their code because it looks like crap at the end. I started with really good code on the first challenge then slowly it turned into crap by the end lol

My code did found the stairs and moved north/south back and forth until my character was level=2+current_floor that was I knew I was ready for the boss.

[ChrFriedel]

I am a little surprised about the few posts in this thread too, so i wanted to ask about others optimization. For Instance my VB.Net Bot has a Automap function with which he maps the current level und always head direct to the nearest unvisited room until he finds the stairs. after that he steps randomly out of the room and back in until he gains enough levels so that playerlvl>dungeonlevel + NumberOf Deaths. Sadly i didnt implement something fancy with the items. My bot just grabs every item he finds and uses no potions.

Any other good ideas?

[dxer]

Did it in bash, character walks around randomly but descends only if the difference between character and dungeon level is high enough. It also implements potion management (2 aquamarine and 1 not-aquamarine) and picking up the strongest weapon. Potions are used if HP reaches 1/3 or 2/3 of maximum HP respectively.

Code: Select all

#!/bin/bash

cookie="$(cat cookie)"
url='http://www.hacker.org/challenge/misc/d/cavern.php'
potion=1

echo "Wait a second :)"
code="$(curl -s -b"$(cat cookie)" "$url")"

function move
{
	moves=( $(echo "$code" | egrep -o 'm=[^d]') )
	index=$(( $(head -c1 /dev/urandom | binary2ascii -bd) % ${#moves[*]} ))
	cmd="${moves[$index]}"
}

while sleep 0.15s
do
	code="$(curl -s -b"$(cat cookie)" "$url?$cmd")"
	echo "$code" | egrep --color=always '[^>]*!|Down|[A-Za-z]* potion( \+[0-9])?|Pick up treasure:|'
	
	stats=( $(echo "$code" | grep "^<tr><td>" | tr -c "[:digit:]\n" " " | sed 's/  */ /g') )
	weapon="$(echo "$code" | grep "^<tr><td>" | egrep -o "Level [^<]*")"
	level="$(echo "$code" | egrep -o "Dungeon Level [0-9]+" | tr -d -c "[:digit:]")"
	maxhp=$(( 20*${stats[0]} + 80 ))
	inventory=$(echo "$code" | sed -n '/Inventory/,/td/p' | grep potion | wc -l)
	cmd=""

	if [[ $code == *killed* ]] || [[ $code == *dragon* ]]; then potion=1; fi



	if [[ $code == *tres=* ]]; then

		newitem="$(echo "$code" | grep "tres=")"
		newweapon="$(echo "$newitem" | egrep -o "Level [^<]*")"
		old=( ${weapon//+/ } 0 )
		new=( ${newweapon//+/ } 0 ) 

		if [ -n "$newweapon" ]; then
			if [ $(( ${new[1]} + ${new[3]} )) -gt $(( ${old[1]} + ${old[3]} )) ]; then
				cmd="tres=1"
			else
				move
			fi
		else
	       		if [ "$inventory" -lt 2 ] && [[ $newitem == *marine* ]]; then 
				cmd="tres=1"
			elif [ "$inventory" -eq 2 ] && [[ $newitem != *marine* ]]; then
				cmd="tres=1"
			else
				move
			fi
		fi

	elif [[ $code == *You*have*died* ]]; then
		exit 0
	elif [[ $code == *reset=* ]]; then
		exit 1
	elif [[ $code == *attack=* ]]; then

		if [ ${stats[1]} -le $(( $maxhp / 3 )) ]; then
			cmd="$(echo "$code" | grep -i aqua | sort -k4 | head -n1 | egrep -o 'potion=.')"
		fi

		if [ ${stats[1]} -le $(( $maxhp / 3 * 2 )) ] && [ $potion -eq 1 ]; then 
			cmd="${cmd:-"$(echo "$code" | grep potion | grep -vi aqua | sort -k4 | head -n1 | egrep -o "potion=.")"}"
			cmd="${cmd:-"attack=1"}"
			potion=0
		else
			cmd="${cmd:-"attack=1"}"
		fi

	elif [[ $code == *m=d* ]] && [ ${stats[0]} -ge $(($level/20 + $level + 3)) ]; then 
		cmd="m=d"
	else
		move
	fi



	echo -e "\E[36mDungeon Level $level"
	echo -e "\E[32mStats: Level ${stats[0]} \t Hitpoints ${stats[1]} \t Experience ${stats[2]} \t\t\E[35m $weapon"
	echo -e "\E[33msending $cmd...\E[0m"

	if [[ $code == *dragon* ]]; then
		echo -e '\E[01;41m DRAGON FOUND! \E[0m'
	fi
done

[gandhi]

finally

Did it with an Userscript (GreaseMonkey).

To pass values form one siteload to the next, i attached parameters to the url.
Something like this:
....hacker.org/challenge/misc/d/cave.php?reset=1&lastMove=e&currentTile=0&takenTiles=100000000&navMode=normal...

My KI worked roughly like this:
(1) move downstairs if you already moved more than 70 times in a level.
(2) if stairs had been found earlier, move back and forward till (1) is true.
(3) if dungeonLevel 24 had been reached, stop bot.

Than i prepared for the endboss manually and killed him

[Tabun]

I used a combination of a local PHP proxy page and a javascript/iframe combination (to avoid the CSS block for javascript). This overcomplicates some things, while keeping others simple (I guess it's just a weird kind of selective laziness). I ended up using a database to store the frequency of (types of) messages showing up.

Needed close to 13000 pageloads. Killed 1762 monsters. Picked up 838 treasures and quaffed 610 potions.
Turns I hit 50.20% of attacks, and monsters hit me 50.24% of the time (gee, would that be by cointoss?).


Fun fact: I actually somehow thought the 1900 move limit was for this 128-dungeon-level-deep challenge, not the next one, so I thought my solution was really tremendously awful with ~3600 moves and ~7800 attacks to get to the end. I guess it wasn't so bad. Still not great, but at least in the ball park.