Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
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:

__END__ C:\test>1031775.pl { 14 => "E", 49 => "I", 75 => "N", 81 => "R", 128 => "W", 178 => "Q", 180 => "X", 189 => "V", 199 => "S", 354 => "O", 359 => "J", 403 => "G", 485 => "T", 492 => "Z", 554 => "B", 603 => "M", 604 => "K", 608 => "Y", 632 => "C", 749 => "D", 779 => "P", 795 => "L", 846 => "U", 864 => "F", 921 => "A", 948 => "H", } [ "E", [ "I", [ "N", [ "R", [ "W", [ "Q", [ "X", [ "V", [ "S", [ "O", [ "J", [ "G", [ "T", [ "Z", [ "B", [ "M", [ "K", [ "Y", ["C", ["D", ["P", ["L", ["U", ["F" +, ["A", ["H", []]]]]]]]], ], ], ], ], ], ], ], ], ], ], ], ], ], ], ], ], ], ]

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 avoiding work at the Monastery: (9)
As of 2014-12-26 20:04 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (175 votes), past polls