Gluk (Kazan) RatTailНасчет твоих предложений : это как мертвому припарки. Если не ломит, пропость сюда мой код с твоими техническими поправками и мы увидим еще один отсос.


сколько заплатишь ?
меня и читать то его ломает (так что я пожалуй ограничусь бесплатными советами)

Но могу сказать точно, в своей работе (а я пользую C++ давно и плотно) с описанными тобой проблемами не встречался.
так об том же и речь! то что можно прочитать в доке я и сам прочитаю
как "тока" так сразу, в кусты; а мне пардон пистёж про скиму и пр. поебень тоже малоинтересен.
Вот Тим Питерс например не постеснялся спросить у "пацанов" про "память" (сорри, не могу найти конкретно тот топик; ему кстати НИКТО не ответил; жуки-сцуки):
http://www.spoj.pl/forum/search.php?search_author=UncleTimmy&sid=6cec3685bb2f9f34b723ebcb661c72c7
а здесь сразу амбиции, "сколько платишь" (эт ваще не фпестуневкраснуармию)

Gluk (Kazan)2 RatTail

Кстати, именно то что долго работает как раз и связано с тем карманным биллиардом, который устаривает STL с твоими векторами как значениями :) так что не надо про припарки

В C++ очень легко прострелить себе ногу
ну дык нах ваще тут упоминать C#, этот чуть ускоренный питон?
а что питон -- это зверь! я это сразу понял; лучше языка вообще быть не может.
Тим Питерс -- это один из его разработчиков.

Gluk (Kazan) RatTailа здесь сразу амбиции, "сколько платишь" (эт ваще не фпестуневкраснуармию)

А кто сказал, что я должен бесплатно делать за тебя твою работу ?
Иди читай документацию

Кстати, на слабо я как правило тоже не ведусь ;)

P.S. Всем пока и до понедельника
моя работа - это детский лепет; насчет "на слабо не ведусь" -- не ну... ваще учись от Тима решать "зодачи" ("проблемы") (только не понятно кто ему платил)

Posted: Sun Nov 27, 2005 19:53 Post subject: Re: POUR1 - Need help with testing strategies

--------------------------------------------------------------------------------

Chen Dingming Benedict wrote:
...
The program still seems to run into errors. I'm suspecting that something might have gone wrong for cases where the min. number of steps required is very large. It's hard to work out such cases using pen and paper... does anyone have a set of test cases/good testing strategies to recommend?

I first wrote a brute-force solver, doing a breadth-first search over all possible states. "A state" here is a pair <a, b> of integers, meaning that vessel A currently contains `a` litres and vessel B `b` litres. The initial state is <0, 0> (both vessels empty). A straightforward, reliable solver then looks like:
Code:
states := a list containing <0, 0>
nsteps := 0
while states is not empty:
nsteps := nsteps + 1
# new_states will be a list of all states that require
# at least nsteps steps to reach for the first time
new_states := an empty list
for each state in states:
for each way of getting a new state newstate from state:
# which means we can empty either vessel, fill
# either vessel, or transfer as much as possible
# from either vessel to the other
if we haven't seen newstate before:
append newstate to new_states
if the target number is in newstate:
return nsteps
states := new_states
return -1 # failure -- not possible

Now that's too slow to get accepted (at least when coded in Python ), but is "obviously correct" so can be used to check other algorithms. The trick isn't to try to speed it, it's to leave the code so bloody obvious that you trust its results 100%.

After that, I wrote a driver to generate test cases at random (picked capacities and a target each uniformly at random from 1 .. 10000), and checked to see that the method above gave the same answer as my then-current "fast" algorithm.

I found that relatively small upper limits were good enough to provoke failure modes. For example, with capacities of 5 and 1, and a target of 3, my first "fast" algorithm attempt assumed (for some reason I can't remember now ) that "fill the smaller vessel first" was a winning strategy, so went through these states:
Code:
0 0
0 1
1 0
1 1
2 0
2 1
3 0

while the brute-force solver found the best sequence:
Code:
0 0
5 0
4 1
4 0
3 1

Your mileage may vary, but I tended to make stupid mistakes like that one, and random testing on small inputs was all it really needed to find them. If I were to do it over again, I'd do exhaustive testing up to a small limit, on all <capacity1, capacity2, target> triples with no element larger than (say) 17.