Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
PerlMonks  

Re: Challenge: Optimal Animals/Pangolins Strategy

by BrowserUk (Pope)
on May 02, 2013 at 16:34 UTC ( #1031781=note: print w/ replies, xml ) Need Help??


in reply to Challenge: Optimal Animals/Pangolins Strategy

You just end up with a really lopsided tree:

#! perl -slw use strict; use Data::Dump qw[ pp ]; use List::Util qw[ reduce ]; our $N //= 1; my %byFreq = map{ int( rand 1000 ) => $_ } 'A'x$N .. 'Z'x$N; pp \%byFreq; my @tree; reduce{ $a->[0] = $byFreq{ $b }; $a->[1] = []; } \@tree, sort{ $a <=> $b } keys %byFreq; pp \@tree;

Output:


With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.


Comment on Re: Challenge: Optimal Animals/Pangolins Strategy
Select or Download Code
Re^2: Challenge: Optimal Animals/Pangolins Strategy
by Limbic~Region (Chancellor) on May 02, 2013 at 17:35 UTC
    BrowserUk,
    You just end up with a really lopsided tree

    Then I must have made a mistake in my explanation because the solution should be closer to Huffman coding as roboticus astutely concluded above. Since I can't explain why what I am trying to accomplish is slightly different, I guess I am stuck.

    Cheers - L~R

      Well, you mentioned proportional which I interpreted to mean that higher frequencies should take longer to reach than lower frequencies, which barring the possibility of equal frequencies, a lop-sided tree achieves.

      (Albeit you said inversely proportional which would mean reversing the order of the sort from what I posted.)

      The only other sense I can get from the information provided -- brought on by the mention of Huffman -- is that you are perhaps looking to minimise the depth of the tree. This does that by building a heap and then converting it to a tree rather clumbsily. Though that could be fixed if the idea is right:

      #! perl -slw use strict; use Data::Dump qw[ pp ]; use List::Util qw[ reduce ]; use enum qw[ NAME FREQ LEFT RIGHT ]; our $N //= 1; my$n = 0; my @heap = map{ $_->[LEFT] = ++$n; $_->[RIGHT] = ++$n; $_; } sort { $a->[FREQ] <=> $b->[FREQ] } map[ $_ , int( rand 1000 ) ], 'A'x$N .. 'Z'x$N;; my @tree = map { $_->[LEFT] = $heap[ $_->[LEFT] ], $_->[RIGHT] = $heap[ $_->[RIGHT] ] } @heap; pp \@tree;

      Output:

      C:\test>1031775.pl do { my $a = [ [ "Y", 1, [ "G", 4, [ "D", 166, ["X", 245, ["I", 516, undef, undef], ["O", 563, undef, undef +]], ["K", 315, ["M", 628, undef, undef], ["R", 710, undef, undef +]], ], [ "A", 218, ["P", 324, ["T", 731, undef, undef], ["Q", 732, undef, undef +]], ["J", 374, ["V", 735, undef, undef], ["C", 835, undef, undef +]], ], ], [ "E", 33, [ "U", 220, ["L", 393, ["S", 845, undef, undef], ["F", 930, undef, undef +]], ["W", 471, ["Z", 944, undef, undef], undef], ], ["H", 228, ["B", 507, undef, undef], ["N", 515, undef, undef]] +, ], ], 'fix', 'fix', 'fix', 'fix', 'fix', 'fix', 'fix', 'fix', 'fix', 'fix', 'fix', 'fix', 'fix', 'fix', 'fix', 'fix', 'fix', 'fix', 'fix', 'fix', 'fix', 'fix', 'fix', 'fix', 'fix', ]; $a->[1] = $a->[0][2]; $a->[2] = $a->[0][3]; $a->[3] = $a->[0][2][2]; $a->[4] = $a->[0][2][3]; $a->[5] = $a->[0][3][2]; $a->[6] = $a->[0][3][3]; $a->[7] = $a->[0][2][2][2]; $a->[8] = $a->[0][2][2][3]; $a->[9] = $a->[0][2][3][2]; $a->[10] = $a->[0][2][3][3]; $a->[11] = $a->[0][3][2][2]; $a->[12] = $a->[0][3][2][3]; $a->[13] = $a->[0][3][3][2]; $a->[14] = $a->[0][3][3][3]; $a->[15] = $a->[0][2][2][2][2]; $a->[16] = $a->[0][2][2][2][3]; $a->[17] = $a->[0][2][2][3][2]; $a->[18] = $a->[0][2][2][3][3]; $a->[19] = $a->[0][2][3][2][2]; $a->[20] = $a->[0][2][3][2][3]; $a->[21] = $a->[0][2][3][3][2]; $a->[22] = $a->[0][2][3][3][3]; $a->[23] = $a->[0][3][2][2][2]; $a->[24] = $a->[0][3][2][2][3]; $a->[25] = $a->[0][3][2][3][2]; $a; }

      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
      /div
        BrowserUk,
        By inversely proportional, I meant that the number of questions asked to identify an animal (Q) multiplied by how many times the animal is chosen (C) should be constant. If a goat appears a hundred times more often than a unicorn then it should take a hundred times more questions to identify the unicorn than the goat.

        I apologize for not seeing it before hand, but I am pretty sure the optimal strategy for my problem is in fact Huffman Coding. To get a better idea of the fuzzy problem I am dealing with in my head, see Re^4: Challenge: Optimal Animals/Pangolins Strategy

        Cheers - L~R

      Aren't Huffman trees generally expected to be lop-sided?

        jakeease,
        I think that depends heavily on the frequency distribution.

        Cheers - L~R

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1031781]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (10)
As of 2014-07-29 23:15 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (229 votes), past polls