Function Always Returns Zero

Talk about things C/C++, some related to AutoHotkey

Do you know what's wrong with this function?

Poll ended at 15 Jan 2020, 16:57

I know exactly what's wrong.
0
No votes
I can spot a flaw(s), but I don't know if solving it would fix the problem.
0
No votes
I don't understand this function.
0
No votes
Everything looks fine to me.
0
No votes
 
Total votes: 0
1100++
Posts: 78
Joined: 10 Feb 2018, 19:05

Function Always Returns Zero

30 Dec 2019, 16:49

I'm trying write a function that will solve the following problem:

Suppose you have a deck of n cards, some of which belong to certain classes. What is the probability of drawing c_i cards out of the total s_i in the deck for each of these classes i, given that you are allowed to draw k cards from the deck and given r opportunities to return all the cards that you drew that did not match your search and then draw a number of cards equal to the number you returned?

n, k, and r are passed as individual parameters, while the s_i and c_i are passed in pairs as an array, along with the size of the array. The main function called is DrawChanceEx(), and the answer is stored in the parameter answer.

For whatever reason, the below function always returns zero. Can someone tell me what's wrong? (Code Updated)

Code: Select all

#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>


using namespace std;


typedef struct {
	__int64 s;
	__int64 c;
} CardReq;

typedef struct {
	__int64 s;
	__int64 c;
	__int64 h = 0;
	__int64 i = 0;
	__int64 s_h;
	__int64 n_ss;
	__int64 n_ss_hh;
	__int64 min_hh = 0;
	__int64 min_cc;
	bool drawn = false;
} CardEx;

typedef struct {
	__int64 hh = 0;
	vector<CardEx> cardlist;
} CardListEx;

typedef struct {
	__int64 ss;
	__int64 cc;
	__int64 n_ss;
	uintptr_t count;
	uintptr_t mcount;
	vector<CardListEx> cards;
} DrawEx;

bool DrawChanceEx(double& answer, __int64 n, __int64 k, __int64 r, uintptr_t count, CardReq DrawReqs[]);

double DrawChanceEx_Draw(const __int64& n, const __int64& k, const __int64& r, DrawEx& DrawArray);

double DrawChanceEx_NextDraw(const __int64& n, const __int64& k, const __int64& r, DrawEx& DrawArray);

__int64 DrawChanceEx_RecurseFinal(const __int64& k, const __int64& ii, const uintptr_t& Level, DrawEx& DrawArray);

double DrawChanceEx_Recurse(const __int64& n, const __int64& k, const __int64& r, const __int64& ii, const uintptr_t& Level,
		DrawEx& DrawArray);

__int64 DrawChance_nCr(const __int64& n, const __int64& k);

__int64 nCr_int64(const __int64& n, const __int64& k);

int main() {
	double answer;
	CardReq cards[] {{4, 2}, {2, 1}, {2, 2}};
	DrawChanceEx(answer, 28, 8, 3, 6, cards);
	cout << answer;
	return 0;
}

bool DrawChanceEx(double& answer, __int64 n, __int64 k, __int64 r, uintptr_t count, CardReq DrawReqs[]) {
	static CardEx ph;
	uintptr_t isc = 0; __int64 ss = 0, cc = 0; CardListEx cards; cards.cardlist.resize(count >>= 1);
	for (struct {uintptr_t i; CardEx& card;} loop {0, ph}; loop.i < count; ++loop.i) {
		if (DrawReqs[loop.i].s < 0 or DrawReqs[loop.i].c < 0)
			return false;
		if (DrawReqs[loop.i].s < DrawReqs[loop.i].c)
			++isc;
		loop.card = cards.cardlist[loop.i];
		loop.card.s = DrawReqs[loop.i].s;
		loop.card.c = DrawReqs[loop.i].c;
		ss += loop.card.s; cc += loop.card.c;
		loop.card.s_h = loop.card.s;
		loop.card.n_ss_hh = loop.card.n_ss = n - ss;
	} if (n < ss)
		return false;
	if (k < cc or isc > 0) {
		answer = 0; return true;
	} for (uintptr_t i = 0; i < count; i++)
		cards.cardlist[i].min_cc = cc -= cards.cardlist[i].c;
	DrawEx DrawArray {ss, cc, n - ss, count, count - 1};
	DrawArray.cards.resize(r + 1); DrawArray.cards[r] = cards;
	answer = DrawChanceEx_Draw(n, k, r, DrawArray);
	return true;
}

double DrawChanceEx_Draw(const __int64& n, const __int64& k, const __int64& r, DrawEx& DrawArray) {
	return (r == 0 ? (double) DrawChanceEx_RecurseFinal(k, 0, 0, DrawArray) : DrawChanceEx_Recurse(n, k, r, 0, 0, DrawArray))
		/ DrawChance_nCr(n - DrawArray.cards[r].hh, k - DrawArray.cards[r].hh);
}

double DrawChanceEx_NextDraw(const __int64& n, const __int64& k, const __int64& r, DrawEx& DrawArray) {
	static CardEx ph;
	CardListEx& cards = DrawArray.cards[r - 1] = DrawArray.cards[r];
	cards.hh = 0;
	for (struct {uintptr_t i; CardEx& card;} loop {0, ph}; loop.i < DrawArray.count; ++loop.i) {
		loop.card = cards.cardlist[loop.i];
		cards.hh += loop.card.h = min(loop.card.i, loop.card.c);
		loop.card.s_h = loop.card.s - loop.card.h; loop.card.i = 0;
	} if (r > 1)
        for (struct {uintptr_t i; __int64 hh; CardEx& card;} loop {0, cards.hh, ph}; loop.i < DrawArray.count; ++loop.i) {
			loop.card = cards.cardlist[loop.i];
			loop.card.n_ss_hh = loop.card.n_ss - cards.hh;
			loop.card.min_hh = loop.hh -= loop.card.h;
		}
	else
		for (uintptr_t i = 0; i < DrawArray.count; i++)
			cards.cardlist[i].n_ss_hh = cards.cardlist[i].n_ss - cards.hh;
	return DrawChanceEx_Draw(n, k, r - 1, DrawArray);
}

__int64 DrawChanceEx_RecurseFinal(const __int64& k, const __int64& ii, const uintptr_t& Level, DrawEx& DrawArray) {
	if (Level == DrawArray.count)
		return DrawChance_nCr(DrawArray.n_ss, k - ii);
	CardEx& card = DrawArray.cards[0].cardlist[Level];
	__int64 sum = 0;
	for (__int64 i = max(card.c, k - ii - card.n_ss_hh), limit = min(card.s, k - ii - card.min_cc); i <= limit; i++)
		sum += DrawChance_nCr(card.s_h, i - card.h) * DrawChanceEx_RecurseFinal(k, ii + i, Level + 1, DrawArray);
	return sum;
}

double DrawChanceEx_Recurse(const __int64& n, const __int64& k, const __int64& r, const __int64& ii, const uintptr_t& Level,
		DrawEx& DrawArray) {
	CardEx& card = DrawArray.cards[r].cardlist[Level];
	double sum = 0; __int64 i = max(card.h, k - ii - card.n_ss_hh), limit = min(card.s, k - ii - card.min_hh);
	if (Level == DrawArray.mcount) {
		for (; i < card.c; i++)
			sum += DrawChance_nCr(card.s_h, i - card.h) * DrawChance_nCr(DrawArray.n_ss, k - ii - (card.i = i))
				* DrawChanceEx_NextDraw(n, k, r, DrawArray);
		__int64 a_sum = 0;
		for (; i <= limit; i++)
			a_sum += DrawChance_nCr(card.s_h, i - card.h) * DrawChance_nCr(DrawArray.n_ss, k - ii - (card.i = i));
		sum += a_sum * (Level == 0 or DrawArray.cards[r].cardlist[Level - 1].drawn ? 1 : DrawChanceEx_NextDraw(n, k, r, DrawArray));
	} else {
		card.drawn = false;
		for (; i < card.c; i++)
			sum += DrawChance_nCr(card.s_h, i - card.h) * DrawChanceEx_Recurse(n, k, r, ii + (card.i = i), Level + 1, DrawArray);
		card.drawn = Level == 0 or DrawArray.cards[r].cardlist[Level - 1].drawn;
		for (; i <= limit; i++)
			sum += DrawChance_nCr(card.s_h, i - card.h) * DrawChanceEx_Recurse(n, k, r, ii + (card.i = i), Level + 1, DrawArray);
	} return sum;
}

__int64 DrawChance_nCr(const __int64& n, const __int64& k) {
	return nCr_int64(n, n >> 1 < k ? n - k : k);
}

__int64 nCr_int64(const __int64& n, const __int64& k) {
	static map<__int64, vector<__int64>*> nCkMemory;
	static __int64 maxMem = 0x200000, count = 0;
	if (k < 2)
		return k ? n : 1;
	__int64 old_k, start;
	if (nCkMemory.count(n)) {
		if (k <= (*nCkMemory[n])[0])
			return (*nCkMemory[n])[k - 1];
		old_k = (*nCkMemory[n])[0];
		start = old_k + 1;
		nCkMemory[n]->reserve(k);
	} else {
		old_k = 0; start = 2;
		nCkMemory[n] = new vector<__int64>;
		nCkMemory[n]->reserve(k);
	}
	__int64 requestedCapacity = k - old_k + count;
	if (requestedCapacity > maxMem) {{
		auto i = nCkMemory.end();
		do {
			requestedCapacity -= (*i->second)[0];
			delete i->second;
			nCkMemory.erase(i--);
		} while (requestedCapacity > maxMem);
	}} __int64 nCk = n, nCk_div;
	for (__int64 i = start, n_i = n - start + 1; i <= k; ++i, --n_i)
		(*nCkMemory[n])[i - 1] = nCk = (nCk_div = nCk / i) * n_i + (nCk - i * nCk_div) * n_i / i;
	(*nCkMemory[n])[0] = k; count = requestedCapacity;
	return nCk;
 }
Running the above code produces this error:

Code: Select all

---------------------------
Microsoft Visual C++ Runtime Library
---------------------------
Debug Assertion Failed!

Program: C:\Users\Main\source\repos\Test 5\Debug\Test 5.exe
File: C:\Program Files (x86)\Microsoft Visual Studio\2019\Community\VC\Tools\MSVC\14.24.28314\include\vector
Line: 1502

Expression: vector subscript out of range

For information on how your program can cause an assertion
failure, see the Visual C++ documentation on asserts.

(Press Retry to debug the application)

---------------------------
Abort   Retry   Ignore   
---------------------------

Return to “C/C++”

Who is online

Users browsing this forum: No registered users and 2 guests