https://www.codingame.com/training/medium/huffman-code
Send your feedback or ask for help here!
Created by @Crypticsy,validated by @chouch,@Apfeloxid and @Gorbit99.
If you have any issues, feel free to ping them.
The expected response for test case #2 does not follow from the problem statement.
(IMHO best to just remove it, it doesnāt bring anything to the puzzle)
2 Likes
You are right, but if you remove it, then you can simply copy-paste your solution to the Addāem up problem because thatās the only difference. So I would recommend to slightly clarify the statement instead.
1 Like
ā¦or remove the puzzle.
Interesting Puzzle. But i did not get what is wrong with my code. All tests are ok, but after submitting my code, the validator 6 fails.
I have two questions about the problem statement:
The problem is describing a specific greedy algorithm for constructing the Huffman tree, but the output is asking for the āleast number of bitsā which implies that there might be different ways of constructing the tree. It is probably possible to construct a better tree than the one constructed with the greedy algorithm, but finding the optimal one should be NP-complete (itās similar to Knapsack problem). So I think the problem statement should clarify that you are to find the amount of bits needed for the encoding using the greedy algorithm, not any algorithm.
The second question is regarding which subtrees we are joining. In all the examples in the statement the joined subtrees are next to each other in alphabetical order. I assume that itās a coincidence, and you can join any two subtrees, not just the neighbor ones. Is this correct?
The Huffman coding is optimal as a prefix binary code on the original alphabet (itās not optimal in more general settings though), it minimizes the size of the resulting encoded text: āįµ¢ |code(textįµ¢)|. I sketched the proof here in the forum (in the context of this other equivalent problem I mentioned above).
The ordering of the subtrees in the example seems arbitrary. The āneighbor onesā does not mean anything, or more precisely, it only means something if you assume that you can only merge neighbor trees starting from an original ordering that would still have to be defined. So no, you can join whichever subtrees you want at any point.
1 Like
Hmm. Looks like you are right, the Huffman code is optimal.
Hi,
Would it be possible to have a second simple test (with 5 or 6 elements) to get a better understanding of the problem, because my code is okay for the two firsts tests and I cannot see why the other tests donāt workā¦
Thanks for this nice problem 
Hi. Iāve been struggling to finish this while itās Puzzle of the Week. I have until tomorrow, and I am sure that Iāve come across a problem in something. If I donāt get this solved by tomorrow night, Iāll go nuts. I donāt have 20 hours every week to devote to solving one puzzle.
Iām keeping all the ātreesā in a multiset, compared according to depth first and weight second; any tree that becomes part of another has its depth offset to push it to the end of the multiset.
I know thatās not how youāre supposed to do it. I just want to make it work one time!
Now, when I create an iterator to the beginning of the multiset, and dereference that iterator, it tells me it is CONST qualified!!!
/tmp/Answer.cpp:94:38: error: passing āconst Treeā as āthisā argument discards qualifiers [-fpermissive]
94 | treeItA->setDepth( tempDepth + 1000 );
| ^
/tmp/Answer.cpp:39:10: note: in call to āvoid Tree::setDepth(int)ā
39 | void setDepth(int d){ depth = d; }
I didnāt make it const!!
According to https://www.cplusplus.com/reference/set/multiset/begin/
" If the multiset object is const-qualified, the function returns a const_iterator. Otherwise, it returns an iterator."
I do have some const qualifiers. They are on the getWeight() method, the getDepth() method, and the compare struct:
struct treeCompare{
bool operator() (const Tree& a, const Tree& b) const {
int ad = a.getDepth();
int bd = b.getDepth();
if( ad == bd ){
return a.getWeight() < b.getWeight();
}
else{ return ad < bd; }
}
};
Because it doesnāt work without them.
Now, my question: Why is the .begin() iterator CONSTANT?
Does the multiset convert every object to const when you use const arguments for the compare function?? Because that sounds absurd. It means any non-const multiset cannot use a custom compare struct.
My code is ugly and embarrassing, but this is the only part giving me errors right now, and I cannot fathom why.
Iāve tried manually casting the .begin() iterator to a pointer to class Tree, as I found on stackoverflow, and I still get this error:
error: binding reference of type āTree&ā to āconst Treeā discards qualifers
Tree& lastTree = *treeItA;
That is wrong. There is no āconst Treeā anywhere in my code.
The iterator returned by begin() for a multiset should not be const.
I named that reference ālastTreeā because it was my last attempt.
Why is begin() returning const for a multiset?
Thanks for any insight. It would be great if it helped me finish the puzzle of the week while itās still puzzle of the week, but even if I go nuts and give up CodinGame, Iāll still be relieved to know why this happened.
I found another way to offset the depth within a class method, so I donāt have to call it.
Now, on calling the CONSTRUCTOR, it refuses to let me do it because the &Tree arguments are supposedly const. Here is my loop:
while(!workingDepth) {
treeItA = all.begin();
if(treeItA->getDepth() >= 1000){
workingDepth = 1;
break;
}
treeItB = all.begin();
treeItB++;
if(treeItB->getDepth() >= 1000){
workingDepth = 1;
break;
}
Tree temp(*treeItA, *treeItB);
all.insert(temp);
}
Here is my output, falsely telling me that my iterators are const:
/tmp/Answer.cpp: In function āint main()ā:
/tmp/Answer.cpp:94:30: error: no matching function for call to āTree::Tree(const Tree&, const Tree&)ā
94 | Tree temp(treeItA, treeItB);
| ^
/tmp/Answer.cpp:20:3: note: candidate: āTree::Tree(Tree, Tree)ā
20 | Tree(Tree* l, Tree* r) {
| ^~~~
/tmp/Answer.cpp:20:14: note: no known conversion for argument 1 from āconst Treeā to āTree*ā
20 | Tree(Tree* l, Tree* r) {
| ~~~^~
/tmp/Answer.cpp:19:3: note: candidate: āTree::Tree(int)ā
19 | Tree(int w) {weight = w; depth=0; leaf = true;}
| ^
/tmp/Answer.cpp:19:3: note: candidate expects 1 argument, 2 provided
/tmp/Answer.cpp:10:7: note: candidate: āconstexpr Tree::Tree(const Tree&)ā
10 | class Tree{
| ^
/tmp/Answer.cpp:10:7: note: candidate expects 1 argument, 2 provided
/tmp/Answer.cpp:10:7: note: candidate: āconstexpr Tree::Tree(Tree&&)ā
/tmp/Answer.cpp:10:7: note: candidate expects 1 argument, 2 provided
/tmp/Answer.cpp:101:29: error: passing āconst Treeā as āthisā argument discards qualifiers [-fpermissive]
101 | if ( treeItA->getLeaf() ) {
| ^ā¦
et<_Key, _Compare, _Alloc>::value_type = Tree]ā
/tmp/Answer.cpp:95:17: required from here
/usr/include/c++/9/bits/stl_tree.h:1807:10: error: no match for call to ā(treeCompare) (const Tree&, const Tree&)ā
/tmp/Answer.cpp:49:10: note: candidate: ābool treeCompare::operator()(Tree&, Tree&) constā
49 | bool operator() (Tree& a, Tree& b) const {
| ^~~~~~~~
/tmp/Answer.cpp:49:10: note: conversion of argument 2 would be ill-formed:
In file included from /usr/include/c++/9/set:60,
from /tmp/Answer.cpp:5:
/usr/include/c++/9/bits/stl_tree.h:1807:10: error: binding reference of type āTree&ā to āconst Treeā discards qualifiers
1806 | bool __insert_left = (__x != 0 || __p == _M_end()
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1807 | || _M_impl._M_key_compare(_KeyOfValue()(__v),
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1808 | _S_key(__p)));
| ~~~~~~~~~~~~~
/usr/include/c++/9/bits/stl_tree.h: In instantiation of āstatic const _Key& std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_S_key(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type) [with _Key = Tree; _Val = Tree; _KeyOfValue = std::_Identity; _Compare = treeCompare; _Alloc = std::allocator; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type = const std::_Rb_tree_node]ā:
/usr/include/c++/9/bits/stl_tree.h:2126:44: required from āstd::pair<std::_Rb_tree_node_base, std::_Rb_tree_node_base*> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_get_insert_equal_pos(const key_type&) [with _Key = Tree; _Val = Tree; _KeyOfValue = std::_Identity; _Compare = treeCompare; _Alloc = std::allocator; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::key_type = Tree]ā
/usr/include/c++/9/bits/stl_tree.h:2175:4: required from āstd::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_equal(_Arg&&) [with _Arg = Tree; _Key = Tree; _Val = Tree; _KeyOfValue = std::_Identity; _Compare = treeCompare; _Alloc = std::allocator; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator = std::_Rb_tree_iterator]ā
/usr/include/c++/9/bits/stl_multiset.h:508:51: required from āstd::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(std::multiset<_Key, _Compare, _Alloc>::value_type&&) [with _Key = Tree; _Compare = treeCompare; _Alloc = std::allocator; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree_const_iterator; std::multiset<_Key, _Compare, _Alloc>::value_type = Tree]ā
/tmp/Answer.cpp:78:22: required from here
/usr/include/c++/9/bits/stl_tree.h:772:16: error: static assertion failed: comparison object must be invocable with two arguments of key type
772 | static_assert(__is_invocable<_Compare&, const _Key&, const _Key&>{},
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
@BanjoMan Itās absolutely impossible (I think) to help you with such partial and messy information about what youāre trying to do and the way you actually do it. Iāll have a look at your code if you send it to me in PM. Note however that solving the puzzle while itās still Puzzle of the Week does not change anything (you earn the same amount of points, there is one achievement for solving the puzzle of the week once, but you can get it any week).
I know, and I wanted that achievement to see what follows it on the āQuest Mapā.
I mean to say that, if I couldnāt solve it in one week (because of time), there wonāt be any week in the near future where I will be able to, as Iām about to start a new job, and I have to stop now because I have an important interview for it Monday morning.
I know my info was spotty, but I identified a very specific problem - the iterator returned by begin() was constant. I did not want to post my code, as I believe that is frowned upon.
I figured out the problem, which was silly: set members cannot be modified, regardless of the iterator. I just spent an hour revamping with a vector, but I still cannot figure out how to: create a new Tree object with left and right pointers to existing Tree objects, indicated by iterators, and add the new Tree to the vector. It appears to reuse the same object each time or something. I believe my problem now would be in memory management, or in using vector<*Tree> instead of vector<Tree>.
Either way, it has proven too much for me in the short time I have. Unfortunately, if I start the new job, I will rarely have time to solve such a hard puzzle within 1 week, and itāll be June before I have any time off. And I hope to get the job. This was the first puzzle-of-the-week in a long time that I looked at and thought āI can do that.ā
For my own mental health, career and family, Iāll have to stay away from CodinGame for a bit.
1 Like
In step 2 of the example why would you join d & e instead of e and (bc)?
I was wondering that, too, but my conclusion is that the final number would be the same. Let me checkā¦
Hi, I just finished this exercise. I struggled understanding how we construct the tree, I visited this link and find it very helpful to grab the idea Huffman Coding | Greedy Algo-3 - GeeksforGeeks, if that can help anyone 