C#•2y ago

✅ Problem with creating algorithm - here is the description: (thank you for any help)

Let us have three cups of integer sizes a, b, c (a, b, c not greater than 10) containing at the beginning x, y, z of water, respectively. We can transfer the water from one cup to other until the cup to is full or the cup from is empty. It is not possible to throw the water out as well as take water from some external source. Input of the program are numbers a, b, c, x, y, z giving the sizes and starting volumes of cups. Program will print the list of all volumes (including zero, if possible) obtainable by transfers (the whole volume must be contained in one cup) and for each of those volumes it prints ":" (colon) and minimal number of transfers needed. Volumes would be printed in ascending order. Example: Input: 4 1 1 1 1 1 Output: 0:1 1:0 2:1 3:2.

81 Replies

Pobiega•2y ago

What have you tried so far?

chills0000OP•2y ago

i dont know if u can see the screenshot attached, but basically i tried going through possible cases and appending a case if its possible, then printing the resulting list..

chills0000OP•2y ago

however the algorithm is not suitable, and would not be able to print the results as it should... do you have any ideas? ideally i would create a class - something like public static void cup_solver() and implement the algorithm there. tried storing all the volumes in one variable, then maybe somehow iterate and find the possible solutions with it, but im not sure...

Pobiega•2y ago

I'd probably use a little bit of OOP here too, having several Cups that each keep track of their current volume and max size then probably make some kind of bool TrySolve(int targetVolume, out int result) method...

chills0000OP•2y ago

what do you mean by oop?

Pobiega•2y ago

object oriented programming

chills0000OP•2y ago

oh okay.. not sure if i know what it means entirely tho, im a beginner. also, you want me to create a bool structure, but i shouldnt be returning true or false, but rather the integer:integer solutions..

Pobiega•2y ago

this is a bit of a tricky problem thou, there are a few "edge cases" to handle

chills0000OP•2y ago

i know, spent a couple hours on it, thats why im asking for help 😄

Pobiega•2y ago

I think you should learn to walk before you try to run 🙂

chills0000OP•2y ago

well, its a school assignment, so /:

Pobiega•2y ago

I don't want to be discouraging, but if the above is your best attempt, you are not ready for this difficulty yet

chills0000OP•2y ago

not necessarily my best attempt, just he most recent stuff i had written lol.. i should delete it ik

Pobiega•2y ago

I've managed to solve it, but it was harder than I expected.

chills0000OP•2y ago

would you maybe have some suggestions or some ideas to guide me a bit please?

Pobiega•2y ago

well the core idea is quite simple we start with a "goal" number of 0 (this is the volume we are trying to reach) then, we try to solve the goal number. If that works, we increase the goal number and we go again repeat until we fail to solve the goal number solving a number is also "straight forward": pick a cup that will be your "target cup". This must be a cup that has size enough for your goal number, but also is the closest to the goal number already. edge case warning: if your goal is below the current volume in all cups.. you have another problem to solve. now, with a target cup picked, we start transfering from the other cups and after each transfer, we check if we have reached the goal. warning: what cup to transfer from matters, you want the lowest number possible of transfers... so we need to find a combination of cups that result in the correct volume in the target cup

chills0000OP•2y ago

why do i need to pick a target cup?

Pobiega•2y ago

well lets take the example given in the description 4 1 1 1 1 1 if your goal is 2 or 3, only one of these cups can actually hold that volume you've "solved" the problem once any of the cups contain the target amount I can think up some truly horrific starting values where the solution will be quite hard to reach ie, the only way to reach the exact target number is to first make a partial transfer from cup A to cup B (filling B, leaving some left in A), THEN transfering from A to C my current solution would not be able to solve that

chills0000OP•2y ago

the cups have 1 volume of water each in them, and their full volumes are 4 1 1. so you cant really transfer from cup A i think. and about the goal num.. i suppose i have to find out whats the largest volume out of those 3 cups?

Pobiega•2y ago

I don't think you should assume the cups sizes are fixed so sure, for the 4 1 1 case, thats truer

chills0000OP•2y ago

no, ofcourse the input nums could be random, i was just referring to what you said.. i thought you were talking about the example provided..

Pobiega•2y ago

well yes. in 4 1 1, goal 0, you can't pick the first cup as your target since you need it to dump from 2nd or 3rd just trying to open your eyes to the complexity here

chills0000OP•2y ago

okay ye i understand what you mean here.. but its kinda hard to implement it into code, satisfying all conditions and other tests..

Pobiega•2y ago

yes. it is. I've not managed to come up with a general solution just yet. Ive solved the example case, but I'm sure it can't handle sneakier inputs

chills0000OP•2y ago

well the numbers are going to be only from 0-10..

Pobiega•2y ago

sure, which keeps the number of iterations down. and there are never more than 3 cups, so a brute force solution will actually do quite nicely. just try every single permutation of transfers for every goal

chills0000OP•2y ago

wouldnt there be quite a lot of permutations in case all the cups are of size 10?

Pobiega•2y ago

not really you'll end up in a locked state at some point where you can shift numbers around, but you cant make new ones

chills0000OP•2y ago

would it be possible to use a bfs algorithm here to improve the brute force algo?

Pobiega•2y ago

hm, that could work.. each possible transfer is an edge, leading to new possible transfers

chills0000OP•2y ago

okay, could you maybe lead me on with some beginning changes so i can pick up on it? not sure where to start changing the code.. introduce some kind of iteration, but not sure how.

Pobiega•2y ago

well you know how BFS/DFS work right?

chills0000OP•2y ago

yep

Pobiega•2y ago

well so make a queue/stack and while that isnt empty, keep searching your initial state will be the starting cups, 0 moves, and your possible "directions" are each cup moving to every other cup

chills0000OP•2y ago

okay i know that, but how do i work with it? what values will i be putting and removing from the queue?

Pobiega•2y ago

I'm envisioning it like a tree where each node in the tree is a state of all three cups and each edge is a possible move you'll need to keep a list of solved states, I guess.

chills0000OP•2y ago

chills0000OP•2y ago

okay so in the brackets in the queue initiations, there should be like what, 4 parameters? 3 are states of the cups, one possible move? or

Pobiega•2y ago

nah you'll have 6 initial possible moves 2 for each cup

chills0000OP•2y ago

what values do i enque here? and then after each enque, i check and update the states of the volumes in the cups currently.. but how?

Pobiega•2y ago

I would enqueue the entire state of all the cups, if a certain move is taken so at a minimum 3 integers

chills0000OP•2y ago

okay, here is some changed and improved version i came up with collective power of my colleague xd. could you check it out? the problem seems to be with the state class, and of course the way of solving the problem a bit..

message.txt

Pobiega•2y ago

$paste

MODiX•2y ago

If your code is too long, you can post to https://paste.mod.gg/ and copy the link into chat for others to see your shared code!

Pobiega•2y ago

I made a BFS version, solves the example nicely.

chills0000OP•2y ago

the link u sent is empty..

Pobiega•2y ago

its for YOU to paste on I'm not giving you my solution.

chills0000OP•2y ago

oh okay sorry lol

Pobiega•2y ago

A general rule we have on this discord is that we don't spoonfeed, especially not on assignments or homework as that would be cheating

chills0000OP•2y ago

okay i saved it

Pobiega•2y ago

paste the link

chills0000OP•2y ago

https://paste.mod.gg/mvweoskqppkx/0

BlazeBin - mvweoskqppkx

A tool for sharing your source code with the world!

Pobiega•2y ago

HashSet to store the state seems a bit curious

chills0000OP•2y ago

nah i was not tryna get the solution from u, just thought you maybe sent some notes for the creation of the queue or something, wasnt sure what do u mean by curious

Pobiega•2y ago

Why a hashset?

chills0000OP•2y ago

seemed like a good idea, also were taught it recently in lectures so why not (supposed we should implement it if we are taught such topics)

Pobiega•2y ago

whats the unique property a hashset has over an array or a list?

chills0000OP•2y ago

would not store duplicate elements (to store the possible cases properly, would not have to check if we have repeating values)

Pobiega•2y ago

indeed

MODiX•2y ago

Pobiega#2671

REPL Result: Success

var set = new HashSet<int>
{
5,
5,
5
};

foreach (var i in set)
{
Console.WriteLine(i);
}

var set = new HashSet<int>
{
5,
5,
5
};

foreach (var i in set)
{
Console.WriteLine(i);
}

Console Output

Compile: 602.141ms | Execution: 52.096ms | React with ❌ to remove this embed.

Pobiega•2y ago

is this really something you want here? if your state is (4,1,1) it would be (4,1) when "loaded" imho, stick to an array, or even better, a struct or record.

chills0000OP•2y ago

the state is 1 1 1, 4 1 1 are the highest volumes of the cups

Pobiega•2y ago

okay thats even worse (1,1,1) would give you just (1)

chills0000OP•2y ago

oh ye true.. okay thanks wtf how did i not see that haha my bad

Pobiega•2y ago

int first = currentStateList[0];
int second = currentStateList[1];
int third = currentStateList[2];

int first = currentStateList[0];
int second = currentStateList[1];
int third = currentStateList[2];

what do you think these lines will do when you only have 1 item?

chills0000OP•2y ago

nono i see whats the problem now ye

Pobiega•2y ago

so make your own struct for state, imho

public record struct State(int A, int B, int C);

public record struct State(int A, int B, int C);

all you need. I need to head off now, its late as heck here but you're on the right track, just need to clean up your code a bit

chills0000OP•2y ago

okay thanks for all.

Pobiega•2y ago

I can show you this

private bool TrySolve(int goal, out int moves)
{
    var queue = new Queue<State>();
    queue.Enqueue(InitialState);

    while (queue.Count > 0)
    {
        var state = queue.Dequeue();

        if (state.Solves(goal))
        {
            moves = state.Moves;
            return true;
        }

        foreach (var possibleState in GetPossibleStates(state))
        {
            queue.Enqueue(possibleState);
        }
    }

    moves = 0;
    return false;
}

private bool TrySolve(int goal, out int moves)
{
    var queue = new Queue<State>();
    queue.Enqueue(InitialState);

    while (queue.Count > 0)
    {
        var state = queue.Dequeue();

        if (state.Solves(goal))
        {
            moves = state.Moves;
            return true;
        }

        foreach (var possibleState in GetPossibleStates(state))
        {
            queue.Enqueue(possibleState);
        }
    }

    moves = 0;
    return false;
}

thats the function that "does all the work" for me

chills0000OP•2y ago

hm okay thanks much

Pobiega•2y ago

GetPossibleStates and state.Solves(goal) are fairly trivial to implement, if a bit lengthy 🙂

chills0000OP•2y ago

should i try to use recursion with bfs here maybe?

Pobiega•2y ago

if you want. I don't

chills0000OP•2y ago

okay

Pobiega•2y ago

BFS was a good idea thou, gotta hand it to ya didnt think of that myself

chills0000OP•2y ago

ty was thinking about recursion with bfs tho, i need that code memory and time complexity optimized..

Pobiega•2y ago

Recursion isn't very memory or time effective in C#, no tail recursion

chills0000OP•2y ago

hm okay then

Pobiega•2y ago

You just end up with more stackframes for no real benefit And here it's easy enough to just break it up like i did

chills0000OP•2y ago

good point..

Accord•2y ago

Was this issue resolved? If so, run /close - otherwise I will mark this as stale and this post will be archived until there is new activity.

Gaming

Programming

✅ Problem with creating algorithm - here is the description: (thank you for any help)