Arbitrary Length Hashing

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
7
down vote

favorite












Consider you have a hash function $mathcalH$ which takes strings of length $2n$ and returns strings of length $n$ and has the nice property that it is collision resistant, i.e. it is hard to find two different strings $s neq s'$ with the same hash $mathcalH(s) = mathcalH(s')$.



You would now like to build a new hash function $mathcalH'$ which takes strings of arbitrary length and maps them to strings of length $n$, while still being collision resistant.



Lucky for you, already in 1979 a method now known as the Merkle–Damgård construction was published which achieves exactly this.



The task of this challenge will be to implement this algorithm, so we'll first have a look at a formal description of the Merkle–Damgård construction, before going through a step-by-step example which should show that the approach is simpler than it might appear at first.




Given some integer $n > 0$, a hash function $mathcalH$ as
described above and an input string $s$ of arbitrary
length, the new hash function $mathcalH'$ does the following:



  • Set $ l = |s|$, the length of $s$, and split $s$ in chunks of length $n$, filling up the last chunk with trailing zeros if
    necessary. This yields $m = lceil fracln rceil $ many chunks
    which are labeled $c_1, c_2, dots, c_m $.

  • Add a leading and a trailing chunk $c_0$ and $c_m+1$, where $c_0$ is a string consisting of $n$ zeros and $c_m+1$ is $n$ in binary, padded with leading zeros to length $n$.

  • Now iteratively apply $mathcalH$ to the current chunk $c_i$ appended to the previous result $r_i-1$: $ r_i =
    mathcalH(r_i-1c_i)$
    , where $r_0 = c_0$. (This step might be
    more clear after looking at the example below.)


  • The output of $mathcalH'$ is the final result $r_m+1$.



The Task



Write a program or function which takes as input a positive integer $n$, a hash function $mathcalH$ as black box and a non-empty string $s$ and returns the same result as $mathcalH'$ on the same inputs.



This is code-golf, so the shortest answer in each language wins.



Example



Let's say $n = 5$, so our given hash function $mathcalH$ takes strings of length 10 and returns strings of length 5.



  • Given an input of $s = texttt"Programming Puzzles" $, we get the following chunks: $s_1 = texttt"Progr" $, $s_2 = texttt"ammin" $, $s_3 = texttt"g Puz" $ and $s_4 = texttt"zles0" $. Note that $s_4$ needed to be padded to length 5 with one trailing zero.


  • $ c_0 = texttt"00000"$ is just a string of five zeros and $ c_5 = texttt"00101"$ is five in binary ($texttt101$), padded with two leading zeros.

  • Now the chunks are combined with $mathcalH$:
    $r_0 = c_0 = texttt"00000" $
    $ r_1 = mathcalH(r_0c_1) = mathcalH(texttt"00000Progr")$
    $ r_2 = mathcalH(r_1c_2) = mathcalH(mathcalH(texttt"00000Progr")texttt"ammin")$
    $ r_3 = mathcalH(r_2c_3) = mathcalH(mathcalH(mathcalH(texttt"00000Progr")texttt"ammin")texttt"g Puz")$
    $ r_4 = mathcalH(r_3c_4) = mathcalH(mathcalH(mathcalH(mathcalH(texttt"00000Progr")texttt"ammin")texttt"g Puz")texttt"zles0")$
    $ r_5 = mathcalH(r_4c_5) = mathcalH(mathcalH(mathcalH(mathcalH(mathcalH(texttt"00000Progr")texttt"ammin")texttt"g Puz")texttt"zles0")texttt"00101")$


  • $r_5$ is our output.

Let's have a look how this output would look depending on some choices1 for $mathcalH$:



  • If $mathcalH(texttt"0123456789") = texttt"13579"$, i.e. $mathcalH$ just returns every second character, we get:
    $r_1 = mathcalH(texttt"00000Progr") = texttt"00Por"$
    $r_2 = mathcalH(texttt"00Porammin") = texttt"0oamn"$
    $r_3 = mathcalH(texttt"0oamng Puz") = texttt"omgPz"$
    $r_4 = mathcalH(texttt"omgPzzles0") = texttt"mPze0"$
    $r_5 = mathcalH(texttt"mPze000101") = texttt"Pe011"$

    So $texttt"Pe011"$ needs to be the output if such a $mathcalH$ is given as black box function.

  • If $mathcalH$ simply returns the first 5 chars of its input, the output of $mathcalH'$ is $texttt"00000"$. Similarly if $mathcalH$ returns the last 5 chars, the output is $texttt"00101"$.

  • If $mathcalH$ multiplies the character codes of its input and returns the first five digits of this number, e.g. $mathcalH(texttt"PPCG123456") = texttt"56613"$, then $mathcalH'(texttt"Programming Puzzles") = texttt"91579"$.


1 For simplicity, those $mathcalH$ are actually not collision resistant, though this does not matter for testing your submission.










share|improve this question





















  • Sandbox (deleted)
    – Laikoni
    1 hour ago














up vote
7
down vote

favorite












Consider you have a hash function $mathcalH$ which takes strings of length $2n$ and returns strings of length $n$ and has the nice property that it is collision resistant, i.e. it is hard to find two different strings $s neq s'$ with the same hash $mathcalH(s) = mathcalH(s')$.



You would now like to build a new hash function $mathcalH'$ which takes strings of arbitrary length and maps them to strings of length $n$, while still being collision resistant.



Lucky for you, already in 1979 a method now known as the Merkle–Damgård construction was published which achieves exactly this.



The task of this challenge will be to implement this algorithm, so we'll first have a look at a formal description of the Merkle–Damgård construction, before going through a step-by-step example which should show that the approach is simpler than it might appear at first.




Given some integer $n > 0$, a hash function $mathcalH$ as
described above and an input string $s$ of arbitrary
length, the new hash function $mathcalH'$ does the following:



  • Set $ l = |s|$, the length of $s$, and split $s$ in chunks of length $n$, filling up the last chunk with trailing zeros if
    necessary. This yields $m = lceil fracln rceil $ many chunks
    which are labeled $c_1, c_2, dots, c_m $.

  • Add a leading and a trailing chunk $c_0$ and $c_m+1$, where $c_0$ is a string consisting of $n$ zeros and $c_m+1$ is $n$ in binary, padded with leading zeros to length $n$.

  • Now iteratively apply $mathcalH$ to the current chunk $c_i$ appended to the previous result $r_i-1$: $ r_i =
    mathcalH(r_i-1c_i)$
    , where $r_0 = c_0$. (This step might be
    more clear after looking at the example below.)


  • The output of $mathcalH'$ is the final result $r_m+1$.



The Task



Write a program or function which takes as input a positive integer $n$, a hash function $mathcalH$ as black box and a non-empty string $s$ and returns the same result as $mathcalH'$ on the same inputs.



This is code-golf, so the shortest answer in each language wins.



Example



Let's say $n = 5$, so our given hash function $mathcalH$ takes strings of length 10 and returns strings of length 5.



  • Given an input of $s = texttt"Programming Puzzles" $, we get the following chunks: $s_1 = texttt"Progr" $, $s_2 = texttt"ammin" $, $s_3 = texttt"g Puz" $ and $s_4 = texttt"zles0" $. Note that $s_4$ needed to be padded to length 5 with one trailing zero.


  • $ c_0 = texttt"00000"$ is just a string of five zeros and $ c_5 = texttt"00101"$ is five in binary ($texttt101$), padded with two leading zeros.

  • Now the chunks are combined with $mathcalH$:
    $r_0 = c_0 = texttt"00000" $
    $ r_1 = mathcalH(r_0c_1) = mathcalH(texttt"00000Progr")$
    $ r_2 = mathcalH(r_1c_2) = mathcalH(mathcalH(texttt"00000Progr")texttt"ammin")$
    $ r_3 = mathcalH(r_2c_3) = mathcalH(mathcalH(mathcalH(texttt"00000Progr")texttt"ammin")texttt"g Puz")$
    $ r_4 = mathcalH(r_3c_4) = mathcalH(mathcalH(mathcalH(mathcalH(texttt"00000Progr")texttt"ammin")texttt"g Puz")texttt"zles0")$
    $ r_5 = mathcalH(r_4c_5) = mathcalH(mathcalH(mathcalH(mathcalH(mathcalH(texttt"00000Progr")texttt"ammin")texttt"g Puz")texttt"zles0")texttt"00101")$


  • $r_5$ is our output.

Let's have a look how this output would look depending on some choices1 for $mathcalH$:



  • If $mathcalH(texttt"0123456789") = texttt"13579"$, i.e. $mathcalH$ just returns every second character, we get:
    $r_1 = mathcalH(texttt"00000Progr") = texttt"00Por"$
    $r_2 = mathcalH(texttt"00Porammin") = texttt"0oamn"$
    $r_3 = mathcalH(texttt"0oamng Puz") = texttt"omgPz"$
    $r_4 = mathcalH(texttt"omgPzzles0") = texttt"mPze0"$
    $r_5 = mathcalH(texttt"mPze000101") = texttt"Pe011"$

    So $texttt"Pe011"$ needs to be the output if such a $mathcalH$ is given as black box function.

  • If $mathcalH$ simply returns the first 5 chars of its input, the output of $mathcalH'$ is $texttt"00000"$. Similarly if $mathcalH$ returns the last 5 chars, the output is $texttt"00101"$.

  • If $mathcalH$ multiplies the character codes of its input and returns the first five digits of this number, e.g. $mathcalH(texttt"PPCG123456") = texttt"56613"$, then $mathcalH'(texttt"Programming Puzzles") = texttt"91579"$.


1 For simplicity, those $mathcalH$ are actually not collision resistant, though this does not matter for testing your submission.










share|improve this question





















  • Sandbox (deleted)
    – Laikoni
    1 hour ago












up vote
7
down vote

favorite









up vote
7
down vote

favorite











Consider you have a hash function $mathcalH$ which takes strings of length $2n$ and returns strings of length $n$ and has the nice property that it is collision resistant, i.e. it is hard to find two different strings $s neq s'$ with the same hash $mathcalH(s) = mathcalH(s')$.



You would now like to build a new hash function $mathcalH'$ which takes strings of arbitrary length and maps them to strings of length $n$, while still being collision resistant.



Lucky for you, already in 1979 a method now known as the Merkle–Damgård construction was published which achieves exactly this.



The task of this challenge will be to implement this algorithm, so we'll first have a look at a formal description of the Merkle–Damgård construction, before going through a step-by-step example which should show that the approach is simpler than it might appear at first.




Given some integer $n > 0$, a hash function $mathcalH$ as
described above and an input string $s$ of arbitrary
length, the new hash function $mathcalH'$ does the following:



  • Set $ l = |s|$, the length of $s$, and split $s$ in chunks of length $n$, filling up the last chunk with trailing zeros if
    necessary. This yields $m = lceil fracln rceil $ many chunks
    which are labeled $c_1, c_2, dots, c_m $.

  • Add a leading and a trailing chunk $c_0$ and $c_m+1$, where $c_0$ is a string consisting of $n$ zeros and $c_m+1$ is $n$ in binary, padded with leading zeros to length $n$.

  • Now iteratively apply $mathcalH$ to the current chunk $c_i$ appended to the previous result $r_i-1$: $ r_i =
    mathcalH(r_i-1c_i)$
    , where $r_0 = c_0$. (This step might be
    more clear after looking at the example below.)


  • The output of $mathcalH'$ is the final result $r_m+1$.



The Task



Write a program or function which takes as input a positive integer $n$, a hash function $mathcalH$ as black box and a non-empty string $s$ and returns the same result as $mathcalH'$ on the same inputs.



This is code-golf, so the shortest answer in each language wins.



Example



Let's say $n = 5$, so our given hash function $mathcalH$ takes strings of length 10 and returns strings of length 5.



  • Given an input of $s = texttt"Programming Puzzles" $, we get the following chunks: $s_1 = texttt"Progr" $, $s_2 = texttt"ammin" $, $s_3 = texttt"g Puz" $ and $s_4 = texttt"zles0" $. Note that $s_4$ needed to be padded to length 5 with one trailing zero.


  • $ c_0 = texttt"00000"$ is just a string of five zeros and $ c_5 = texttt"00101"$ is five in binary ($texttt101$), padded with two leading zeros.

  • Now the chunks are combined with $mathcalH$:
    $r_0 = c_0 = texttt"00000" $
    $ r_1 = mathcalH(r_0c_1) = mathcalH(texttt"00000Progr")$
    $ r_2 = mathcalH(r_1c_2) = mathcalH(mathcalH(texttt"00000Progr")texttt"ammin")$
    $ r_3 = mathcalH(r_2c_3) = mathcalH(mathcalH(mathcalH(texttt"00000Progr")texttt"ammin")texttt"g Puz")$
    $ r_4 = mathcalH(r_3c_4) = mathcalH(mathcalH(mathcalH(mathcalH(texttt"00000Progr")texttt"ammin")texttt"g Puz")texttt"zles0")$
    $ r_5 = mathcalH(r_4c_5) = mathcalH(mathcalH(mathcalH(mathcalH(mathcalH(texttt"00000Progr")texttt"ammin")texttt"g Puz")texttt"zles0")texttt"00101")$


  • $r_5$ is our output.

Let's have a look how this output would look depending on some choices1 for $mathcalH$:



  • If $mathcalH(texttt"0123456789") = texttt"13579"$, i.e. $mathcalH$ just returns every second character, we get:
    $r_1 = mathcalH(texttt"00000Progr") = texttt"00Por"$
    $r_2 = mathcalH(texttt"00Porammin") = texttt"0oamn"$
    $r_3 = mathcalH(texttt"0oamng Puz") = texttt"omgPz"$
    $r_4 = mathcalH(texttt"omgPzzles0") = texttt"mPze0"$
    $r_5 = mathcalH(texttt"mPze000101") = texttt"Pe011"$

    So $texttt"Pe011"$ needs to be the output if such a $mathcalH$ is given as black box function.

  • If $mathcalH$ simply returns the first 5 chars of its input, the output of $mathcalH'$ is $texttt"00000"$. Similarly if $mathcalH$ returns the last 5 chars, the output is $texttt"00101"$.

  • If $mathcalH$ multiplies the character codes of its input and returns the first five digits of this number, e.g. $mathcalH(texttt"PPCG123456") = texttt"56613"$, then $mathcalH'(texttt"Programming Puzzles") = texttt"91579"$.


1 For simplicity, those $mathcalH$ are actually not collision resistant, though this does not matter for testing your submission.










share|improve this question













Consider you have a hash function $mathcalH$ which takes strings of length $2n$ and returns strings of length $n$ and has the nice property that it is collision resistant, i.e. it is hard to find two different strings $s neq s'$ with the same hash $mathcalH(s) = mathcalH(s')$.



You would now like to build a new hash function $mathcalH'$ which takes strings of arbitrary length and maps them to strings of length $n$, while still being collision resistant.



Lucky for you, already in 1979 a method now known as the Merkle–Damgård construction was published which achieves exactly this.



The task of this challenge will be to implement this algorithm, so we'll first have a look at a formal description of the Merkle–Damgård construction, before going through a step-by-step example which should show that the approach is simpler than it might appear at first.




Given some integer $n > 0$, a hash function $mathcalH$ as
described above and an input string $s$ of arbitrary
length, the new hash function $mathcalH'$ does the following:



  • Set $ l = |s|$, the length of $s$, and split $s$ in chunks of length $n$, filling up the last chunk with trailing zeros if
    necessary. This yields $m = lceil fracln rceil $ many chunks
    which are labeled $c_1, c_2, dots, c_m $.

  • Add a leading and a trailing chunk $c_0$ and $c_m+1$, where $c_0$ is a string consisting of $n$ zeros and $c_m+1$ is $n$ in binary, padded with leading zeros to length $n$.

  • Now iteratively apply $mathcalH$ to the current chunk $c_i$ appended to the previous result $r_i-1$: $ r_i =
    mathcalH(r_i-1c_i)$
    , where $r_0 = c_0$. (This step might be
    more clear after looking at the example below.)


  • The output of $mathcalH'$ is the final result $r_m+1$.



The Task



Write a program or function which takes as input a positive integer $n$, a hash function $mathcalH$ as black box and a non-empty string $s$ and returns the same result as $mathcalH'$ on the same inputs.



This is code-golf, so the shortest answer in each language wins.



Example



Let's say $n = 5$, so our given hash function $mathcalH$ takes strings of length 10 and returns strings of length 5.



  • Given an input of $s = texttt"Programming Puzzles" $, we get the following chunks: $s_1 = texttt"Progr" $, $s_2 = texttt"ammin" $, $s_3 = texttt"g Puz" $ and $s_4 = texttt"zles0" $. Note that $s_4$ needed to be padded to length 5 with one trailing zero.


  • $ c_0 = texttt"00000"$ is just a string of five zeros and $ c_5 = texttt"00101"$ is five in binary ($texttt101$), padded with two leading zeros.

  • Now the chunks are combined with $mathcalH$:
    $r_0 = c_0 = texttt"00000" $
    $ r_1 = mathcalH(r_0c_1) = mathcalH(texttt"00000Progr")$
    $ r_2 = mathcalH(r_1c_2) = mathcalH(mathcalH(texttt"00000Progr")texttt"ammin")$
    $ r_3 = mathcalH(r_2c_3) = mathcalH(mathcalH(mathcalH(texttt"00000Progr")texttt"ammin")texttt"g Puz")$
    $ r_4 = mathcalH(r_3c_4) = mathcalH(mathcalH(mathcalH(mathcalH(texttt"00000Progr")texttt"ammin")texttt"g Puz")texttt"zles0")$
    $ r_5 = mathcalH(r_4c_5) = mathcalH(mathcalH(mathcalH(mathcalH(mathcalH(texttt"00000Progr")texttt"ammin")texttt"g Puz")texttt"zles0")texttt"00101")$


  • $r_5$ is our output.

Let's have a look how this output would look depending on some choices1 for $mathcalH$:



  • If $mathcalH(texttt"0123456789") = texttt"13579"$, i.e. $mathcalH$ just returns every second character, we get:
    $r_1 = mathcalH(texttt"00000Progr") = texttt"00Por"$
    $r_2 = mathcalH(texttt"00Porammin") = texttt"0oamn"$
    $r_3 = mathcalH(texttt"0oamng Puz") = texttt"omgPz"$
    $r_4 = mathcalH(texttt"omgPzzles0") = texttt"mPze0"$
    $r_5 = mathcalH(texttt"mPze000101") = texttt"Pe011"$

    So $texttt"Pe011"$ needs to be the output if such a $mathcalH$ is given as black box function.

  • If $mathcalH$ simply returns the first 5 chars of its input, the output of $mathcalH'$ is $texttt"00000"$. Similarly if $mathcalH$ returns the last 5 chars, the output is $texttt"00101"$.

  • If $mathcalH$ multiplies the character codes of its input and returns the first five digits of this number, e.g. $mathcalH(texttt"PPCG123456") = texttt"56613"$, then $mathcalH'(texttt"Programming Puzzles") = texttt"91579"$.


1 For simplicity, those $mathcalH$ are actually not collision resistant, though this does not matter for testing your submission.







code-golf function hashing






share|improve this question













share|improve this question











share|improve this question




share|improve this question










asked 2 hours ago









Laikoni

18.8k33389




18.8k33389











  • Sandbox (deleted)
    – Laikoni
    1 hour ago
















  • Sandbox (deleted)
    – Laikoni
    1 hour ago















Sandbox (deleted)
– Laikoni
1 hour ago




Sandbox (deleted)
– Laikoni
1 hour ago










3 Answers
3






active

oldest

votes

















up vote
1
down vote














Jelly, 23 bytes



0Ṿ;s;BṾ€ṚWƲ}z”0ZU0¦;Ç¥/


Try it online!



Accepts $mathcal H$ at the line above it, $s$ as its left argument, and $n$ as its right argument.






share|improve this answer



























    up vote
    1
    down vote














    Haskell, 91 bytes





    n!h=h.(++mapM(_->"01")a!!n).(a?)where a='0'<$[1..n];c?""=c;c?z=h(c++take n(z++a))?drop n z


    Try it online!



    Explanation




    a='0'<$[1..n]


    Just assigns the string "00...0" ('0' $n$ times) to a




    c?""=c
    c?z=h(c++take n(z++a))?drop n z


    The function ? implements the recursive application of h: c is the hash we have obtained so far (length $n$), z is the rest of the string. If z is empty then we simply return c, otherwise we take the first $n$ characters of z (eventually padding with zeros from a), concatenate c at the beginning and apply h. This gives the new hash, and then we call ? recursively on this hash and the remaining characters of z.




    n!h=h.(++mapM(_->"01")a!!n).(a?)


    The function ! is the one actually solving the challenge. It takes n, h and s (implicit) as inputs. We compute a?s, and all we have to do is append n in binary and apply h once more. mapM(_->"01")a!!n gets the binary representation of n (here a could be replaced by any string of length n).






    share|improve this answer




















    • let in a guard is shorter than using where: Try it online!
      – Laikoni
      37 mins ago

















    up vote
    0
    down vote














    R, 159 bytes





    function(n,H,s,`+`=paste0,`*`=strrep,`/`=Reduce,`?`=nchar,S=0*n+s+0*(n-(?s)%%n)+"+"/n%/%2^(n:1-1)%%2)(function(x,y)H(x+y))/substring(S,seq(1,?S,n),seq(n,?S,n))


    Try it online!



    Yuck! Answering string challenges in R is never pretty, but this is horrible. This is an instructive answer on how not to write "normal" R code...



    function(n,H,s, # harmless-looking function arguments with horrible default arguments 
    # to prevent the use of and save two bytes
    # then come the default arguments,
    # replacing operators as aliases for commonly used functions:
    `+`=paste0, # paste0 with binary +
    `*`=strrep, # strrep for binary *
    `/`=Reduce, # Reduce with binary /
    `?`=nchar, # nchar with unary ?
    S= # final default argument S, the padded string:
    0*n+ # rep 0 n times
    s+ # the original string
    0*(n-(?s)%%n)+ # 0 padding as a multiple of n
    "+"/n%/%2^(n:1-1)%%2) # n as an n-bit number
    # finally, the function body:
    (function(x,y)H(x+y)) / # Reduce/Fold (/) by H operating on x + y
    substring(S,seq(1,?S,n),seq(n,?S,n)) # operating on the n-length substrings of S




    share




















      Your Answer




      StackExchange.ifUsing("editor", function ()
      return StackExchange.using("mathjaxEditing", function ()
      StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
      StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
      );
      );
      , "mathjax-editing");

      StackExchange.ifUsing("editor", function ()
      StackExchange.using("externalEditor", function ()
      StackExchange.using("snippets", function ()
      StackExchange.snippets.init();
      );
      );
      , "code-snippets");

      StackExchange.ready(function()
      var channelOptions =
      tags: "".split(" "),
      id: "200"
      ;
      initTagRenderer("".split(" "), "".split(" "), channelOptions);

      StackExchange.using("externalEditor", function()
      // Have to fire editor after snippets, if snippets enabled
      if (StackExchange.settings.snippets.snippetsEnabled)
      StackExchange.using("snippets", function()
      createEditor();
      );

      else
      createEditor();

      );

      function createEditor()
      StackExchange.prepareEditor(
      heartbeatType: 'answer',
      convertImagesToLinks: false,
      noModals: false,
      showLowRepImageUploadWarning: true,
      reputationToPostImages: null,
      bindNavPrevention: true,
      postfix: "",
      onDemand: true,
      discardSelector: ".discard-answer"
      ,immediatelyShowMarkdownHelp:true
      );



      );













       

      draft saved


      draft discarded


















      StackExchange.ready(
      function ()
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f173805%2farbitrary-length-hashing%23new-answer', 'question_page');

      );

      Post as a guest






























      3 Answers
      3






      active

      oldest

      votes








      3 Answers
      3






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes








      up vote
      1
      down vote














      Jelly, 23 bytes



      0Ṿ;s;BṾ€ṚWƲ}z”0ZU0¦;Ç¥/


      Try it online!



      Accepts $mathcal H$ at the line above it, $s$ as its left argument, and $n$ as its right argument.






      share|improve this answer
























        up vote
        1
        down vote














        Jelly, 23 bytes



        0Ṿ;s;BṾ€ṚWƲ}z”0ZU0¦;Ç¥/


        Try it online!



        Accepts $mathcal H$ at the line above it, $s$ as its left argument, and $n$ as its right argument.






        share|improve this answer






















          up vote
          1
          down vote










          up vote
          1
          down vote










          Jelly, 23 bytes



          0Ṿ;s;BṾ€ṚWƲ}z”0ZU0¦;Ç¥/


          Try it online!



          Accepts $mathcal H$ at the line above it, $s$ as its left argument, and $n$ as its right argument.






          share|improve this answer













          Jelly, 23 bytes



          0Ṿ;s;BṾ€ṚWƲ}z”0ZU0¦;Ç¥/


          Try it online!



          Accepts $mathcal H$ at the line above it, $s$ as its left argument, and $n$ as its right argument.







          share|improve this answer












          share|improve this answer



          share|improve this answer










          answered 46 mins ago









          Erik the Outgolfer

          29.8k42899




          29.8k42899




















              up vote
              1
              down vote














              Haskell, 91 bytes





              n!h=h.(++mapM(_->"01")a!!n).(a?)where a='0'<$[1..n];c?""=c;c?z=h(c++take n(z++a))?drop n z


              Try it online!



              Explanation




              a='0'<$[1..n]


              Just assigns the string "00...0" ('0' $n$ times) to a




              c?""=c
              c?z=h(c++take n(z++a))?drop n z


              The function ? implements the recursive application of h: c is the hash we have obtained so far (length $n$), z is the rest of the string. If z is empty then we simply return c, otherwise we take the first $n$ characters of z (eventually padding with zeros from a), concatenate c at the beginning and apply h. This gives the new hash, and then we call ? recursively on this hash and the remaining characters of z.




              n!h=h.(++mapM(_->"01")a!!n).(a?)


              The function ! is the one actually solving the challenge. It takes n, h and s (implicit) as inputs. We compute a?s, and all we have to do is append n in binary and apply h once more. mapM(_->"01")a!!n gets the binary representation of n (here a could be replaced by any string of length n).






              share|improve this answer




















              • let in a guard is shorter than using where: Try it online!
                – Laikoni
                37 mins ago














              up vote
              1
              down vote














              Haskell, 91 bytes





              n!h=h.(++mapM(_->"01")a!!n).(a?)where a='0'<$[1..n];c?""=c;c?z=h(c++take n(z++a))?drop n z


              Try it online!



              Explanation




              a='0'<$[1..n]


              Just assigns the string "00...0" ('0' $n$ times) to a




              c?""=c
              c?z=h(c++take n(z++a))?drop n z


              The function ? implements the recursive application of h: c is the hash we have obtained so far (length $n$), z is the rest of the string. If z is empty then we simply return c, otherwise we take the first $n$ characters of z (eventually padding with zeros from a), concatenate c at the beginning and apply h. This gives the new hash, and then we call ? recursively on this hash and the remaining characters of z.




              n!h=h.(++mapM(_->"01")a!!n).(a?)


              The function ! is the one actually solving the challenge. It takes n, h and s (implicit) as inputs. We compute a?s, and all we have to do is append n in binary and apply h once more. mapM(_->"01")a!!n gets the binary representation of n (here a could be replaced by any string of length n).






              share|improve this answer




















              • let in a guard is shorter than using where: Try it online!
                – Laikoni
                37 mins ago












              up vote
              1
              down vote










              up vote
              1
              down vote










              Haskell, 91 bytes





              n!h=h.(++mapM(_->"01")a!!n).(a?)where a='0'<$[1..n];c?""=c;c?z=h(c++take n(z++a))?drop n z


              Try it online!



              Explanation




              a='0'<$[1..n]


              Just assigns the string "00...0" ('0' $n$ times) to a




              c?""=c
              c?z=h(c++take n(z++a))?drop n z


              The function ? implements the recursive application of h: c is the hash we have obtained so far (length $n$), z is the rest of the string. If z is empty then we simply return c, otherwise we take the first $n$ characters of z (eventually padding with zeros from a), concatenate c at the beginning and apply h. This gives the new hash, and then we call ? recursively on this hash and the remaining characters of z.




              n!h=h.(++mapM(_->"01")a!!n).(a?)


              The function ! is the one actually solving the challenge. It takes n, h and s (implicit) as inputs. We compute a?s, and all we have to do is append n in binary and apply h once more. mapM(_->"01")a!!n gets the binary representation of n (here a could be replaced by any string of length n).






              share|improve this answer













              Haskell, 91 bytes





              n!h=h.(++mapM(_->"01")a!!n).(a?)where a='0'<$[1..n];c?""=c;c?z=h(c++take n(z++a))?drop n z


              Try it online!



              Explanation




              a='0'<$[1..n]


              Just assigns the string "00...0" ('0' $n$ times) to a




              c?""=c
              c?z=h(c++take n(z++a))?drop n z


              The function ? implements the recursive application of h: c is the hash we have obtained so far (length $n$), z is the rest of the string. If z is empty then we simply return c, otherwise we take the first $n$ characters of z (eventually padding with zeros from a), concatenate c at the beginning and apply h. This gives the new hash, and then we call ? recursively on this hash and the remaining characters of z.




              n!h=h.(++mapM(_->"01")a!!n).(a?)


              The function ! is the one actually solving the challenge. It takes n, h and s (implicit) as inputs. We compute a?s, and all we have to do is append n in binary and apply h once more. mapM(_->"01")a!!n gets the binary representation of n (here a could be replaced by any string of length n).







              share|improve this answer












              share|improve this answer



              share|improve this answer










              answered 43 mins ago









              Delfad0r

              823213




              823213











              • let in a guard is shorter than using where: Try it online!
                – Laikoni
                37 mins ago
















              • let in a guard is shorter than using where: Try it online!
                – Laikoni
                37 mins ago















              let in a guard is shorter than using where: Try it online!
              – Laikoni
              37 mins ago




              let in a guard is shorter than using where: Try it online!
              – Laikoni
              37 mins ago










              up vote
              0
              down vote














              R, 159 bytes





              function(n,H,s,`+`=paste0,`*`=strrep,`/`=Reduce,`?`=nchar,S=0*n+s+0*(n-(?s)%%n)+"+"/n%/%2^(n:1-1)%%2)(function(x,y)H(x+y))/substring(S,seq(1,?S,n),seq(n,?S,n))


              Try it online!



              Yuck! Answering string challenges in R is never pretty, but this is horrible. This is an instructive answer on how not to write "normal" R code...



              function(n,H,s, # harmless-looking function arguments with horrible default arguments 
              # to prevent the use of and save two bytes
              # then come the default arguments,
              # replacing operators as aliases for commonly used functions:
              `+`=paste0, # paste0 with binary +
              `*`=strrep, # strrep for binary *
              `/`=Reduce, # Reduce with binary /
              `?`=nchar, # nchar with unary ?
              S= # final default argument S, the padded string:
              0*n+ # rep 0 n times
              s+ # the original string
              0*(n-(?s)%%n)+ # 0 padding as a multiple of n
              "+"/n%/%2^(n:1-1)%%2) # n as an n-bit number
              # finally, the function body:
              (function(x,y)H(x+y)) / # Reduce/Fold (/) by H operating on x + y
              substring(S,seq(1,?S,n),seq(n,?S,n)) # operating on the n-length substrings of S




              share
























                up vote
                0
                down vote














                R, 159 bytes





                function(n,H,s,`+`=paste0,`*`=strrep,`/`=Reduce,`?`=nchar,S=0*n+s+0*(n-(?s)%%n)+"+"/n%/%2^(n:1-1)%%2)(function(x,y)H(x+y))/substring(S,seq(1,?S,n),seq(n,?S,n))


                Try it online!



                Yuck! Answering string challenges in R is never pretty, but this is horrible. This is an instructive answer on how not to write "normal" R code...



                function(n,H,s, # harmless-looking function arguments with horrible default arguments 
                # to prevent the use of and save two bytes
                # then come the default arguments,
                # replacing operators as aliases for commonly used functions:
                `+`=paste0, # paste0 with binary +
                `*`=strrep, # strrep for binary *
                `/`=Reduce, # Reduce with binary /
                `?`=nchar, # nchar with unary ?
                S= # final default argument S, the padded string:
                0*n+ # rep 0 n times
                s+ # the original string
                0*(n-(?s)%%n)+ # 0 padding as a multiple of n
                "+"/n%/%2^(n:1-1)%%2) # n as an n-bit number
                # finally, the function body:
                (function(x,y)H(x+y)) / # Reduce/Fold (/) by H operating on x + y
                substring(S,seq(1,?S,n),seq(n,?S,n)) # operating on the n-length substrings of S




                share






















                  up vote
                  0
                  down vote










                  up vote
                  0
                  down vote










                  R, 159 bytes





                  function(n,H,s,`+`=paste0,`*`=strrep,`/`=Reduce,`?`=nchar,S=0*n+s+0*(n-(?s)%%n)+"+"/n%/%2^(n:1-1)%%2)(function(x,y)H(x+y))/substring(S,seq(1,?S,n),seq(n,?S,n))


                  Try it online!



                  Yuck! Answering string challenges in R is never pretty, but this is horrible. This is an instructive answer on how not to write "normal" R code...



                  function(n,H,s, # harmless-looking function arguments with horrible default arguments 
                  # to prevent the use of and save two bytes
                  # then come the default arguments,
                  # replacing operators as aliases for commonly used functions:
                  `+`=paste0, # paste0 with binary +
                  `*`=strrep, # strrep for binary *
                  `/`=Reduce, # Reduce with binary /
                  `?`=nchar, # nchar with unary ?
                  S= # final default argument S, the padded string:
                  0*n+ # rep 0 n times
                  s+ # the original string
                  0*(n-(?s)%%n)+ # 0 padding as a multiple of n
                  "+"/n%/%2^(n:1-1)%%2) # n as an n-bit number
                  # finally, the function body:
                  (function(x,y)H(x+y)) / # Reduce/Fold (/) by H operating on x + y
                  substring(S,seq(1,?S,n),seq(n,?S,n)) # operating on the n-length substrings of S




                  share













                  R, 159 bytes





                  function(n,H,s,`+`=paste0,`*`=strrep,`/`=Reduce,`?`=nchar,S=0*n+s+0*(n-(?s)%%n)+"+"/n%/%2^(n:1-1)%%2)(function(x,y)H(x+y))/substring(S,seq(1,?S,n),seq(n,?S,n))


                  Try it online!



                  Yuck! Answering string challenges in R is never pretty, but this is horrible. This is an instructive answer on how not to write "normal" R code...



                  function(n,H,s, # harmless-looking function arguments with horrible default arguments 
                  # to prevent the use of and save two bytes
                  # then come the default arguments,
                  # replacing operators as aliases for commonly used functions:
                  `+`=paste0, # paste0 with binary +
                  `*`=strrep, # strrep for binary *
                  `/`=Reduce, # Reduce with binary /
                  `?`=nchar, # nchar with unary ?
                  S= # final default argument S, the padded string:
                  0*n+ # rep 0 n times
                  s+ # the original string
                  0*(n-(?s)%%n)+ # 0 padding as a multiple of n
                  "+"/n%/%2^(n:1-1)%%2) # n as an n-bit number
                  # finally, the function body:
                  (function(x,y)H(x+y)) / # Reduce/Fold (/) by H operating on x + y
                  substring(S,seq(1,?S,n),seq(n,?S,n)) # operating on the n-length substrings of S





                  share











                  share


                  share










                  answered 3 mins ago









                  Giuseppe

                  15.3k31051




                  15.3k31051



























                       

                      draft saved


                      draft discarded















































                       


                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function ()
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f173805%2farbitrary-length-hashing%23new-answer', 'question_page');

                      );

                      Post as a guest













































































                      Comments

                      Popular posts from this blog

                      What does second last employer means? [closed]

                      Installing NextGIS Connect into QGIS 3?

                      One-line joke