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)
3 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 