Clash 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 choices¹ 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.}

asked 2 hours ago

Laikoni

18.8k33389

Sandbox (deleted)
â€“Â Laikoni
1 hour ago

add a commentÂ |Â

up vote
7
down vote

favorite

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.

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

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 choices¹ 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.}

asked 2 hours ago

Laikoni

18.8k33389

Sandbox (deleted)
â€“Â Laikoni
1 hour ago

add a commentÂ |Â

up vote
7
down vote

favorite

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.

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

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 choices¹ 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.}

asked 2 hours ago

Laikoni

18.8k33389

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.

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

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 choices¹ 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

asked 2 hours ago

Laikoni

18.8k33389

asked 2 hours ago

Laikoni

18.8k33389

asked 2 hours ago

Laikoni

18.8k33389

asked 2 hours ago

Laikoni

18.8k33389

asked 2 hours ago

Laikoni

18.8k33389

Sandbox (deleted)
â€“Â Laikoni
1 hour ago

add a commentÂ |Â

Sandbox (deleted)
â€“Â Laikoni
1 hour ago

Sandbox (deleted)
â€“Â Laikoni
1 hour ago

add a commentÂ |Â

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.

answered 46 mins ago

Erik the Outgolfer

29.8k42899

add a commentÂ |Â

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

answered 43 mins ago

Delfad0r

823213

let in a guard is shorter than using where: Try it online!
â€“Â Laikoni
37 mins ago

add a commentÂ |Â

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

answered 3 mins ago

Giuseppe

15.3k31051

add a commentÂ |Â

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

Name

3 Answers
3

active

oldest

votes

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.

answered 46 mins ago

Erik the Outgolfer

29.8k42899

add a commentÂ |Â

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.

answered 46 mins ago

Erik the Outgolfer

29.8k42899

add a commentÂ |Â

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.

answered 46 mins ago

Erik the Outgolfer

29.8k42899

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.

answered 46 mins ago

Erik the Outgolfer

29.8k42899

answered 46 mins ago

Erik the Outgolfer

29.8k42899

answered 46 mins ago

Erik the Outgolfer

29.8k42899

answered 46 mins ago

Erik the Outgolfer

29.8k42899

add a commentÂ |Â

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

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

answered 43 mins ago

Delfad0r

823213

let in a guard is shorter than using where: Try it online!
â€“Â Laikoni
37 mins ago

add a commentÂ |Â

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

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

answered 43 mins ago

Delfad0r

823213

let in a guard is shorter than using where: Try it online!
â€“Â Laikoni
37 mins ago

add a commentÂ |Â

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

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

answered 43 mins ago

Delfad0r

823213

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

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

answered 43 mins ago

Delfad0r

823213

answered 43 mins ago

Delfad0r

823213

answered 43 mins ago

Delfad0r

823213

answered 43 mins ago

Delfad0r

823213

let in a guard is shorter than using where: Try it online!
â€“Â Laikoni
37 mins ago

add a commentÂ |Â

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

add a commentÂ |Â

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

answered 3 mins ago

Giuseppe

15.3k31051

add a commentÂ |Â

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

answered 3 mins ago

Giuseppe

15.3k31051

add a commentÂ |Â

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

answered 3 mins ago

Giuseppe

15.3k31051

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

answered 3 mins ago

Giuseppe

15.3k31051

answered 3 mins ago

Giuseppe

15.3k31051

answered 3 mins ago

Giuseppe

15.3k31051

answered 3 mins ago

Giuseppe

15.3k31051

add a commentÂ |Â

draft saved

draft discarded

draft saved

draft discarded

Post as a guest

Name

Category

Random preview

Arbitrary Length Hashing

The Task

Example

The Task

Example

The Task

Example

The Task

Example

3 Answers 3

Jelly, 23 bytes

Haskell, 91 bytes

Explanation

R, 159 bytes

Your Answer

Sign up or log in

Post as a guest

Post as a guest

3 Answers 3

3 Answers 3

Jelly, 23 bytes

Jelly, 23 bytes

Jelly, 23 bytes

Jelly, 23 bytes

Haskell, 91 bytes

Explanation

Haskell, 91 bytes

Explanation

Haskell, 91 bytes

Explanation

Haskell, 91 bytes

Explanation

R, 159 bytes

R, 159 bytes

R, 159 bytes

R, 159 bytes

Sign up or log in

Post as a guest

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Comments

Post a Comment

Popular posts from this blog

Long meetings (6-7 hours a day): Being â€œbabysatâ€ by supervisor

Is the Concept of Multiple Fantasy Races Scientifically Flawed? [closed]

Confectionery

3 Answers
3

3 Answers
3

3 Answers
3

Long meetings (6-7 hours a day): Being â€œbabysatâ€ by supervisor