title: Arbitrary Length Hashing

text:
# Question
Title: Arbitrary Length Hashing
Consider you have a hash function \\$\mathcal{H}\\$ 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 \\$\mathcal{H}(s) = \mathcal{H}(s')\\$.

You would now like to build a new hash function \\$\mathcal{H'}\\$ 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 \\$\mathcal{H}\\$ as described above and an input string \\$s\\$ of arbitrary length, the new hash function \\$\mathcal{H'}\\$ 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 \frac{l}{n} \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 \\$\mathcal{H}\\$ to the current chunk \\$c\_i\\$ appended to the previous result \\$r\_{i-1}\\$: \\$ r\_i = \mathcal{H}(r\_{i-1}c\_i)\\$, where \\$r\_0 = c\_0\\$. *(This step might be more clear after looking at the example below.)*
> * The output of \\$\mathcal{H'}\\$ 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 \\$\mathcal{H}\\$ as black box and a non-empty string \\$s\\$ and returns the same result as \\$\mathcal{H'}\\$ on the same inputs.

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

### Example

Let's say \\$n = 5\\$, so our given hash function \\$\mathcal{H}\\$ 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 (\\$\texttt{101}\\$), padded with two leading zeros.
* Now the chunks are combined with \\$\mathcal{H}\\$:
\\$r\_0 = c\_0 = \texttt{"00000"} \\$
\\$ r\_1 = \mathcal{H}(r\_0c\_1) = \mathcal{H}(\texttt{"00000Progr"})\\$
\\$ r\_2 = \mathcal{H}(r\_1c\_2) = \mathcal{H}(\mathcal{H}(\texttt{"00000Progr"})\texttt{"ammin"})\\$ \\$ r\_3 = \mathcal{H}(r\_2c\_3) = \mathcal{H}(\mathcal{H}(\mathcal{H}(\texttt{"00000Progr"})\texttt{"ammin"})\texttt{"g Puz"})\\$
\\$ r\_4 = \mathcal{H}(r\_3c\_4) = \mathcal{H}(\mathcal{H}(\mathcal{H}(\mathcal{H}(\texttt{"00000Progr"})\texttt{"ammin"})\texttt{"g Puz"})\texttt{"zles0"})\\$
\\$ r\_5 = \mathcal{H}(r\_4c\_5) = \mathcal{H}(\mathcal{H}(\mathcal{H}(\mathcal{H}(\mathcal{H}(\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 \\$\mathcal{H}\\$:

* If \\$\mathcal{H}(\texttt{"0123456789"}) = \texttt{"13579"}\\$, i.e. \\$\mathcal{H}\\$ just returns every second character, we get:
\\$r\_1 = \mathcal{H}(\texttt{"00000Progr"}) = \texttt{"00Por"}\\$
\\$r\_2 = \mathcal{H}(\texttt{"00Porammin"}) = \texttt{"0oamn"}\\$
\\$r\_3 = \mathcal{H}(\texttt{"0oamng Puz"}) = \texttt{"omgPz"}\\$
\\$r\_4 = \mathcal{H}(\texttt{"omgPzzles0"}) = \texttt{"mPze0"}\\$
\\$r\_5 = \mathcal{H}(\texttt{"mPze000101"}) = \texttt{"Pe011"}\\$
So \\$\texttt{"Pe011"}\\$ needs to be the output if such a \\$\mathcal{H}\\$ is given as black box function.
* If \\$\mathcal{H}\\$ simply returns the first 5 chars of its input, the output of \\$\mathcal{H'}\\$ is \\$\texttt{"00000"}\\$. Similarly if \\$\mathcal{H}\\$ returns the last 5 chars, the output is \\$\texttt{"00101"}\\$.
* If \\$\mathcal{H}\\$ multiplies the character codes of its input and returns the first five digits of this number, e.g. \\$\mathcal{H}(\texttt{"PPCG123456"}) = \texttt{"56613"}\\$, then \\$\mathcal{H}'(\texttt{"Programming Puzzles"}) = \texttt{"91579"}\\$.

---

1 For simplicity, those \\$\mathcal{H}\\$ are actually not collision resistant, though this does not matter for testing your submission.

# Answer
> 7 votes
# Haskell, ~~91~~ ~~90~~ 86 bytes

```
n!h|let a='0'<$[1..n];c?""=c;c?z=h(c++take n(z++a))?drop n z=h.(++mapM(:"1")a!!n).(a?)

```

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` (possibly padding with zeros from `a`), prepend `c` 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(:"1")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(:"1")a!!n` returns the binary representation of \\$n\\$.

# Answer
> 7 votes
# , ~~159~~ 154 bytes

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

```

Try it online!

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

*Thanks to nwellnhof for fixing a bug, at a cost of 0 bytes!*

*Thanks to J.Doe for swapping the operator aliasing to change the precedence, good for -4 bytes.*

The explanation below is for the previous version of the code, but the principles remain the same.

```
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*-((?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
```

# Answer
> 3 votes
# C (gcc), 251 bytes

```
#define P sprintf(R,
b(_){_=_>1?10*b(_/2)+_%2:_;}f(H,n,x)void(*H)(char*);char*x;{char R[2*n+1],c[n+1],*X=x;P"%0*d",n,0);while(strlen(x)>n){strncpy(c,x,n);x+=n;strcat(R,c);H(R);}P"%s%s%0*d",R,x,n-strlen(x),0);H(R);P"%s%0*d",R,n,b(n));H(R);strcpy(X,R);}

```

Try it online!

Not as clean as the bash solution, and highly improvable.

The function is `f` taking `H` as a function that replaces its string input with that string's hash, `n` as in the description, and `x` the input string and output buffer.

Description:

```
#define P sprintf(R,     // Replace P with sprintf(R, leading to unbalanced parenthesis
                         // This is replaced and expanded for the rest of the description
b(_){                    // Define b(x). It will return the integer binary expansion of _
                         // e.g. 5 -> 101 (still as integer)
  _=_>1?                 // If _ is greater than 1
    10*b(_/2)+_%2        // return 10*binary expansion of _/2 + last binary digit
    :_;}                 // otherwise just _
f(H,n,x)                 // Define f(H,n,x)
  void(*H)(char*);       // H is a function taking a string
  char*x; {              // x is a string
  char R[2*n+1],c[n+1],  // Declare R as a 2n-length string and c as a n-length string
  *X=x;                  // save x so we can overwrite it later
  sprintf(R,"%0*d",n,0); // print 'n' 0's into R
  while(strlen(x)>n){    // while x has at least n characters
    strncpy(c,x,n);x+=n; // 'move' the first n characters of x into c
    strcat(R,c);         // concatenate c and R
    H(R);}               // Hash R
  sprintf(R,"%s%s%0*d"   // set R to two strings concatenated followed by some zeroes
    R,x,                 // the two strings being R and (what's left of) x
    n-strlen(x),0);      // and n-len(x) zeroes
  H(R);                  // Hash R
  sprintf(R,"%s%*d",R,n, // append to R the decimal number, 0 padded to width n
    b(n));               // The binary expansion of n as a decimal number
  H(R);strcpy(X,R);}     // Hash R and copy it into where x used to be

```

# Answer
> 3 votes
# Ruby, 78 bytes

```
->n,s,g{(([?0*n]*2*s).chop.scan(/.{#{n}}/)+["%0#{n}b"%n]).reduce{|s,x|g[s+x]}}

```

Try it online!

### How it works:

```
([?0*n]*2*s).chop    # Padding: add leading and trailing
                     # zeros, then remove the last one
.scan(/.{#{n}}/)     # Split the string into chunks
                     # of length n
+["%0#{n}b"%n]       # Add the trailing block
.reduce{|s,x|g[s+x]} # Apply the hashing function
                     # repeatedly

```

# Answer
> 2 votes
# 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.

# Answer
> 2 votes
# Bash, 127-ε bytes

```
Z=`printf %0*d $1` R=$Z
while IFS= read -rn$1 c;do R=$R$c$Z;R=`H<<<${R::2*$1}`;done
H< <(printf $R%0*d $1 `bc <<<"obase=2;$1"`)

```

Try it online!

This works as a program/function/script/snippet. H must be resolveable to a program or function that will perform the hashing. N is the argument. Example call:

```
$ H() {
>   sed 's/.\(.\)/\1/g'
> }
$ ./wherever_you_put_the_script.sh 5 <<< "Programming Puzzles"  # if you add a shebang
Pe011

```

Description:

```
Z=`printf %0*d $1`

```

This creates a string of `$1` zeroes. This works by calling printf and telling it to print an integer padded to ***extra argument*** width. That extra argument we pass is `$1`, the argument to the program/function/script which stores n.

```
R=$Z

```

This merely copies Z, our zero string, to R, our result string, in preparation for the hashing loop.

```
while IFS= read -rn$1 c; do

```

This loops over the input every `$1` (n) characters loading the read characters into c. If the input ends then c merely ends up too short. The `r` option ensures that any special characters in the input don't get bash-interpreted. This is the  in the title - that `r` isn't strictly necessary, but makes the function more accurately match the input.

```
R=$R$c$Z

```

This concatenates the n characters read from input to R along with zeroes for padding (too many zeroes for now).

```
R=`H<<<${R::2*$1}`;done

```

This uses a here string as input to the hash function. The contents `${R::2*$1}` are a somewhat esoteric bash parameter substitution which reads: R, starting from 0, only 2n characters.

Here the loop ends and we finish with:

```
H< <(printf $R%0*d $1 `bc <<<"obase=2;$1"`)

```

Here the same format string trick is used to 0 pad the number. `bc` is used to convert it to binary by setting the output base (obase) to 2. The result is passed to the hash function/program whose output is not captured and thus is shown to the user.

# Answer
> 2 votes
# Perl 6, ~~79~~ 68 bytes

```
{reduce &^h o&[~],comb 0 x$^n~$^s~$n.fmt("%.{$n-$s.comb%-$n}b"): $n}

```

Try it online!

### Explanation

```
{
  reduce         # Reduce with
    &^h o&[~],   # composition of string concat and hash function
    comb         # Split string
      0 x$^n     # Zero repeated n times
      ~$^s       # Append input string s
      ~$n.fmt("  # Append n formatted
        %.       # with leading zeroes,
        {$n             # field width n for final chunk
         -$s.comb%-$n}  # -(len(s)%-n) for padding,
        b")      # as binary number
      :          # Method call with colon syntax
      $n         # Split into substrings of length n
}

```

# Answer
> 2 votes
# Pyth, 24 bytes

Since Pyth doesn't allow H to be used for a function name, I use `y` instead.

```
uy+GH+c.[E=`ZQQ.[ZQ.BQ*Z

```

Try it online! Example is with the "every second character" version of H.

# Answer
> 1 votes
# GolfScript, 47 bytes

```
~:π'0'*:s\+s+π/);[sπ2base{48+}%+0π->]+{+1$~}*\;

```

Try it online!

# Answer
> 1 votes
# Clean, 143 bytes

```
import StdEnv
r=['0':r]
$n h s=foldl(\a b=h(a++b))(r%(1,n))([(s++r)%(i,i+n-1)\\i<-[0,n..length s]]++[['0'+toChar((n>>(n-p))rem 2)\\p<-[1..n]]])

```

Try it online!

# Answer
> 1 votes
# oK, 41 bytes

```
{(x#48)(y@,)/(0N,x)#z,,/$((x+x!-#z)#2)\x}

```

Try it online!

```
{                                       } /x is n, y is H, z is s.
                          (x+x!-#z)       /number of padding 0's needed + x
                         (         #2)\x  /binary(x) with this length
                      ,/$                 /to string
                    z,                    /append to z
             (0N,x)#                      /split into groups of length x
       (y@,)/                             /foldl of y(concat(left, right))...
 (x#48)                                   /...with "0"*x as the first left string

```

# Answer
> 1 votes
# Python 2, ~~126~~ 113 bytes

```
lambda n,H,s:reduce(lambda x,y:H(x+y),re.findall('.'*n,'0'*n+s+'0'*(n-len(s)%n))+[bin(n)[2:].zfill(n)])
import re

```

Try it online!

-13 thanks to Triggernometry.

Yeah, this is an abomination, why can't I just use a built-in to split a string into chunks...? :-(

# Answer
> 1 votes
# Python 2, ~~106~~ 102 bytes

For once, the function outgolfs the lambda. -4 bytes for simple syntax manipulation, thanks to Jo King.

```
def f(n,H,s):
 x='0'*n;s+='0'*(n-len(s)%n)+bin(n)[2:].zfill(n)
 while s:x=H(x+s[:n]);s=s[n:]
 return x

```

Try it online!

# Answer
> 1 votes
# Japt, 27 bytes

```
òV ú'0 pV¤ùTV)rÈ+Y gOvW}VçT

```

Try it!

I haven't found any capability for Japt to take functions directly as an input, so this takes a string which is interpreted as Japt code and expects it to define a function. Specifically, `OvW` takes the third input and interprets it as Japt, then `g` calls it. Replacing that with `OxW` allows input as a Javascript function instead, or if the function were (somehow) already stored in W it could just be `W` and save 2 bytes. The link above has the worked example of \\$\mathcal{H}\\$ that takes characters at odd indexes, while this one is the "multiply char-codes and take the 5 highest digits" example.

Due to the way Japt takes inputs, \\$s\\$ will be `U`, \\$n\\$ will be `V`, and \\$\mathcal{H}\\$ will be `W`

Explanation:

```
òV                             Split U into segments of length V
   ú'0                         Right-pad the short segment with "0" to the same length as the others
       p     )                 Add an extra element:
        V¤                       V as a base-2 string
          ùTV                    Left-pad with "0" until it is V digits long
              r                Reduce...
                        VçT          ...Starting with "0" repeated V times...
               È       }                                                  ...By applying:
                +Y               Combine with the previous result
                   gOvW          And run W as Japt code
```

---
Tags: code-golf, function, hashing
---


title: Shortest code to secure wipe a disk

text:
# Question
Title: Shortest code to secure wipe a disk
Let's write the shortest code to perform a simplified variant of the DoD 5220.22-M Wipe Method with only two writing passes.

Any programming language accepted, but the use of disk-wiping-oriented libraries is prohibited.

Here's how we are to implement it in pseudocode:

```
Set x to 0

[Start]
'Write Pass
For each sector in disk write the content of x
'Verification Pass
For each sector in disk {
    If sector does not contain the content of x then goto [Start]
}
'Check whether we already did the pass with 1
If x is not 1 then {
    Set x to 1
    GoTo [Start]
}
Else end

```

In other words, this code will run twice, with a write pass and verification pass for `0`, and a write pass and verification pass for `1`.

Anyone ballsy enough to implement it code-golf style? ;)

# Answer
# x86 machine code (Linux), ~~116~~ ~~109~~ 106 bytes

```
00000000: 89cb 6a02 5999 894c 24f4 b005 cd80 505b  ..j.Y..L$.....P[
00000010: 536a 025a 31c9 b013 cd80 89c6 5b53 9931  Sj.Z1.......[S.1
00000020: c9b0 13cd 8089 f75b 53b2 018d 4c24 f8b0  .......[S...L$..
00000030: 04cd 804e 75f1 5b53 9931 c9b0 13cd 8089  ...Nu.[S.1......
00000040: fe5b 538d 4c24 f4b2 01b0 03cd 804e 740c  .[S.L$.......Nt.
00000050: 8a44 24f8 3844 24f4 74e7 ebb3 89fe b001  .D$.8D$.t.......
00000060: 8644 24f8 3c01 75a7 58c3                 .D$.<.u.X.

```

Function that takes filename as argument, uses fastcall convention.

Assembly (NASM):

```
section .text
	global func
func:

	;open file
        mov ebx, ecx	;first argument to func (filename)
	push 0x2	;flag O_RDWR
	pop ecx		;pushing a constant is shorter than mov
	cdq	        ;edx=mode=0
	mov [esp-12], ecx ;set first byte (msg) to write to 0. msg later in esp-8, buf in esp-12
	mov al, 5
	int 0x80	;syscall open
	push eax	;save file descriptor

	write_verify:

	;get file size
	pop ebx		;get fd
	push ebx
	push 0x2	;flag SEEK_END
	pop edx
	xor ecx, ecx 	;offset 0
	mov al, 0x13
	int 0x80	;syscall lseek
	mov esi, eax	;save file byte count in esi

	;reset index of file to 0
	pop ebx		;get fd
	push ebx
	cdq	        ;edx=flag SEEK_SET=0
	xor ecx, ecx	;ecx=0
	mov al, 0x13
	int 0x80	;syscall lseek

	;***write pass***
	mov edi, esi
	write_loop:	;for each byte in byte count, write [msg]
		;write to file
		pop ebx		;file descriptor
		push ebx
		mov dl, 1	;bytes to write
		lea ecx, [esp-8] ;buffer to write from
		mov al, 4
		int 0x80	;syscall write
		dec esi		;decrement (byte count) to 0
		jne write_loop	;while esi!=0, loop

	;reset index of file to 0
	pop ebx		;get fd
	push ebx
	cdq 	        ;edx=SEEK_SET=0
	xor ecx, ecx	;ecx=0
	mov al, 0x13
	int 0x80	;syscall lseek

	;***verification pass***
	mov esi, edi
	verify_loop:	;for each byte in byte count, verify written byte
		pop ebx		;get fd
		push ebx
		lea ecx, [esp-12] ;buffer to store read byte
		mov dl, 1	;read 1 byte
		mov al, 3
		int 0x80	;syscall read
		dec esi
		je end_verify	;at final byte, end verification
		mov al, [esp-8]
		cmp byte [esp-12],al
		je verify_loop	 ;loop if expected value found
		jmp write_verify ;if byte!=expected value, restart

	end_verify:
	mov esi, edi
	mov al, 1
	xchg byte [esp-8],al	;set new byte to write to 1
	cmp al, 1
	jne write_verify	;if old byte to write!=1, goto start

	pop eax			;reset stack
	ret

```

Try it online!

-7 bytes and -3 bytes thanks to @EasyasPi
> 2 votes

# Answer
On a linux system there's no need for special handling of devices. Just use the device file interface.

# Python 3 (byte strings) - 141 bytes

```
d=input()
f=open(d,'r+b')
z=f.seek
z(0,2)
s=f.tell()
i=0
while i<2:
 z(0);f.write([b'\0',b'\xff'][i]*s);f.flush();z(0)
 if f.read()==x:i+=1

```

It's fairly straightforward, and not really optimised heavily, but it works. Here's a basic rundown.

* Get input (device file path)
* Open device file
* Seek to the end, get filesize (block devices are always their real size)
* enter write-and-check loop
* construct 0-bit and 1-bit strings (x)
* write bitstring
* flush output (I could have set buffering=0 but this is shorter)
* test file against x, and increment step of loop if it passes

exit loop when the increment is high enough

As a bonus, you could modify this for any set and number of byte-modification patterns, like 0x55/0xaa for stronger overwriting effects.

I did actually test this on a device file, using loopback. However, I'm not 100% sure the checking actually works. It might be necessary to close and reopen the file each pass, due to buffering behaviors. I would hope flush prevents this.

\*edited to incorporate some suggestions in the comments
> 3 votes

# Answer
# C (clang), `-DZ=lseek(d,0` \+ 139 = 152 bytes

```
g,j,x,d,s,i,c;f(n){x=0;d=open(n,2);s=Z,2);for(j=2;j--;x++){Z,0);for(i=s;i--;write(d,&x,1));Z,0);for(i=s;i--;read(d,&c,1),c!=x&&x--&&j--);}}

```

Try it online!

Takes the filename as an argument

Ungolfed:

```
#include <unistd.h>
int g,j,x,d,s,i,c;
void f(char*n){
	x=0; /*Byte to write*/
	d=open(n,O_RDWR);
	s=lseek(d,0,SEEK_END); /*Get size of file*/
	j=0;
	for(j=0;j<2;j++){
		/*Write Pass*/
		lseek(d,0,SEEK_SET); /*Start writing from start of file*/
		for(i=0;i<s;i++){
			write(d,&x,1);
		}

		/*Verification Pass*/
		lseek(d,0,SEEK_SET);
		for(i=0;i<s;i++){
			read(d,&c,1);
			if(c!=x)x--,j--; /*If verification fails, repeat loop with the same value*/
		}
		x++;
	}
}

```
> 2 votes

# Answer
# Tcl, 286 bytes

```
proc f {o i l} {seek $o 0
set s [string repeat $i $l]
puts -nonewline $o $s
flush $o
seek $o 0
return [string equal [read $o $l] $s]}
set n [open $argv r+]
fconfigure $n -translation binary
seek $n 0 end
set m [tell $n]
while {![f $n "\0" $m]} {}
while {![f $n "\xff" $m]} {}

```

Not really optimized that well. I tried what I could, but I don't know that much about Tcl.

Save as "f.tcl" and run on Unix with `tclsh f.tcl "your filename"`. Make sure there's exactly one argument! I tested this on a plain file, but it should work on a device file as well.

Setting variables and indexing is more involved in Tcl, so I decided to put the common code between the passes into a function. Then I call it first with "\0", and repeat while it fails to verify. I do the same thing with "\xff".

I flushed after writes; it might not be necessary. `fconfigure -translation binary -buffering none` is longer.

-2 bytes by removing quotes around `r+`.
> 1 votes

---
Tags: code-golf
---


title: Split it. But not all!

text:
# Question
Title: Split it. But not all!
Inspired by this StackOverflow question.

## Input:

We'll take three inputs:

* A delimiter-character `D` to split on
* A character `I` between two of which we ignore the delimiter character (I know, that sounds vague, but I'll explain it below)
* A string `S`

## Output:

A list/array containing the substrings after the split.

## Example:

```
Input:
D = ','
I = '"'
S = '11020199,"Abc ",aduz,,444,bieb,dc,2 ,2222.00,whatever 5dc,222.22,22.00,"98,00","12,000,000",21-09-2018, 06:00,",-,"'

Output:
['11020199', 'Abc ', 'aduz', '', '444', 'bieb', 'dc', '2 ', '2222.00', 'whatever 5dc', '222.22', '22.00', '98,00', '12,000,000', '21-09-2018', ' 06:00', ',-,']

```

Why? Splitting on comma would normally also split `98,00`, `12,000,000` and `,-,` in two/three pieces. But because they are within the `I` input character, we ignore ignore the split here.

## Challenge rules:

* You can assume there will always be an even amount of `I` characters in the input-string.
* You can assume the character `I` will always have a `D` next to it (except when it's the first or last character of the input) which can still be properly split. So you won't have something like `D = ','; I = '"'; S = 'a,b"c,d"e,f'`, nor anything like this `D=','; I='"'; S='a",b,"c'`.
* The input-string `S` could contain none of either `D` or `I`. If it contains no `D`, we output a list with the entire input-string as only item.
* The output list won't contain the character `I` anymore, even when it contained no `D` (as you can see at the `"Abc "` becoming `'Abc '` in the example above).
* It is possible that the substring within `I` contains only `D`. For example: `D = ','; I = '"'; S = 'a,",",b,"c","d,e,,",f'` would result in `['a', ',', 'b', 'c', 'd,e,,', 'f']`.
* You can assume that `D` will never be at the start or end of `S`, so you won't have to deal with trailing / leading empty items.
* When an input has two adjacent `D`, we'll have an empty item. I.e. `D = ','; I = '"'; S = 'a,"b,c",d,,e,"",f'` would result in `['a', 'b,c', 'd', '', 'e', '', 'f']`.
* You can assume the inputs and outputs will only contain printable ASCII in the range `[32, 126]` (so excluding tabs and newlines).
* You are also allowed to output all items new-line delimited instead of returning/outputting a list/array (especially for those languages that don't have lists/arrays; i.e. Retina).
* You are allowed to output the list in reversed order if it saves bytes. You are not allowed to output it in sorted or 'shuffled' order, though. So `D = ','; I = 'n'; S = 'a,2,b,3,c'` can be output as `[a,2,b,3,c]` or `[c,3,b,2,a]`, but not as `[2,3,a,b,c,]` or `[a,3,b,c,2]` for example.

## General rules:

* This is , so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
* Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code (i.e. TIO).
* Also, adding an explanation for your answer is highly recommended.

## Test cases:

```
Input:
D = ','; I = '"'; S = 'a,"b,c",d,,e,"",f'
Output:
['a', 'b,c', 'd', '', 'e', '', 'f']

Input:
D = ','; I = '"'; S = '11020199,"Abc ",aduz,,444,bieb,dc,2 ,2222.00,whatever 5dc,222.22,22.00,"98,00","12,000,000",21-09-2018, 06:00,",-,"'
Output:
['11020199', 'Abc ', 'aduz', '', '444', 'bieb', 'dc', '2 ', '2222.00', 'whatever 5dc', '222.22', '22.00', '98,00', '12,000,000', '21-09-2018', ' 06:00', ',-,']

Input:
D = ' '; I = ','; S = 'this is a test , to see if you understand it, or not , hmmm, I think I have too many commas , or not , perhaps..'
Output:
['this', 'is', 'a', 'test', ' to see if you understand it', 'or', 'not', ' hmmm', 'I', 'think', 'I', 'have', 'too', 'many', 'commas', ' or not ', 'perhaps..']

Input:
D = 'x'; I = 'y'; S = 'contains no lowercase X nor Y'
Output:
['contains no lowercase X nor Y']

Input:
D = '1'; I = '3'; S = '3589841973169139975105820974944592078316406286208948254211370679314'
Output: ['58984197', '69', '9975105820974944592078', '64062862089482542', '', '70679', '4']

Input:
D = ' '; I = 'S'; S = 'regular split on spaces'
Output:
['regular', 'split', 'on', 'spaces']

```

# Answer
> 3 votes
# Japt, 16 bytes

```
qV mÏu ?X:XrWRÃq

```

Try it!

Basically the same strategy as DLosc's newer Pip answer, sets aside the "quoted" sections then replaces the delimiter with a newline in the rest of the string, resulting in a newline delimited output

Full explanation:

```
qV                  Split on I
   m          Ã     For each segment:
    Ïu ?              If the segment has an odd index (quoted)...
        X             Keep it as-is
         :          Otherwise:
          XrWR        Replace each D in the segment with a newline
               q    Join it all to a single string

```

Note that even if the first item is quoted, it will still end up at index 1 not index 0. If `q` finds a delimiter as the first character, it makes the first item in the split (index 0) an empty string, so the contents of the quote correctly become the second item (index 1). Here is a demo of correctly dealing with a leading quote.

# Answer
> 9 votes
# , 34 bytes

Regular unmodified `scan` with the appropriate arguments for `text`, `sep` and `quote` should do it.

```
function(D,I,S)scan(,t=S,"",,,D,I)

```

Try it online!

# Answer
> 7 votes
# C (gcc), 64 bytes

```
c;f(d,i,s)char*s;{for(;*s;s++)*s==i?c=!c:putchar(d-*s|c?*s:10);}

```

Try it online!

# JavaScript (Node.js), 57 bytes

```
(d,i,s)=>s.replace(c=/./g,e=>i==e?(c^=1,''):d!=e|c?e:`
`)

```

Try it online!

# Answer
> 5 votes
# Pip, 18 bytes

```
FxcxQb?!:oOo?xRanx

```

Takes inputs as command-line arguments. Try it online!

Completely different approach: process the string one character at a time and output the desired results newline-delimited.

### How?

```
                    a,b,c are cmdline args (respectively representing D,I,S); o is 1;
                    n is newline (implicit)
                    We use o for a flag indicating whether or not to change D into newline
Fxc                 For each character x in c:
   xQb?              If x equals b (the ignore character),
       !:o            Logically negate o in-place
          O          Else, output the following (with no trailing newline):
           o?         If o is truthy,
             xRan      x, with a (the delimiter) replaced with newline
                 x    Else, x unchanged

```

# Answer
> 4 votes
# Python 2, 67 bytes

```
import csv
lambda D,I,S:next(csv.reader(S,delimiter=D,quotechar=I))

```

Try it online!

# Python 2, 71 bytes

```
D,I,S=input()
k=1
for p in S.split(I):print p.replace(D*k,'\n'*k),;k^=1

```

Try it online!

# Answer
> 4 votes
# MATL, 24 bytes

```
y=Yso~yi=*~*cO10Zt2G[]Zt

```

Inputs are `S`, `I`, `D`.

Try it online! Or verify all test cases.

### How it works

Consider inputs `D = ','`; `I = '"'`; `S = 'a,"b,c",d,,e,"",f'`.

```
y     % Implicit inputs: S, I. Duplicate from below
      % STACK: 'a,"b,c",d,,e,"",f', '"', 'a,"b,c",d,,e,"",f'
=     % Is equal? Element-wise
      % STACK: 'a,"b,c",d,,e,"",f', [0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0]
Ys    % Cumulative sum
      % STACK: 'a,"b,c",d,,e,"",f', [0 0 1 1 1 1 2 2 2 2 2 2 2 3 4 4 4]
o~    % Parity, negate
      % STACK: 'a,"b,c",d,,e,"",f', [1 1 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1]
y     % Duplicate from below
      % STACK: 'a,"b,c",d,,e,"",f', [1 1 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1], 'a,"b,c",d,,e,"",f'
i=    % Input: D. Is equal? Element-wise
      % STACK: 'a,"b,c",d,,e,"",f', [1 1 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1], [0 1 0 0 1 0 0 1 0 1 1 0 1 0 0 1 0]
*~    % Multiply, negate (equivalent to NAND). Element-wise
      % STACK: 'a,"b,c",d,,e,"",f', [1 0 1 1 1 1 1 0 1 0 0 1 0 1 1 0 1]
*     % Multiply, element-wise. Characters are converted to ASCII code
      % STACK: [97 0 34 98 44 99 34 0 100 0 0 101 0 34 34 0 102]
c     % Convert to char (character 0 is shown here as '·')
      % STACK: 'a·"b,c"·d··e·""·f'
O10   % Push 0 and then 10
      % STACK: 'a·"b,c"·d··e·""·f', 0, 10
Zt    % Replace character 0 by character 10 (newline; shown here as '¶')
      % STACK: 'a¶"b,c"¶d¶¶e¶""¶f'
2G[]  % Push second input (I) and then [] (empty array)
      % STACK: 'a¶"b,c"¶d¶¶e¶""¶f', '"', []
Zt    % Replace character given by input I by empty; that is, remove it. Implicit display
      % STACK: 'a¶b,c¶d¶¶e¶¶f'

```

# Answer
> 3 votes
# Retina, 45 bytes

```
L$`(?=.*¶(.)¶(.))(\2(.*?)\2|(.*?))(\1|¶)
$4$5

```

Try it online! Explanation:

```
(?=.*¶(.)¶(.))(\2(.*?)\2|(.*?))(\1|¶)

```

Look ahead to find the values of `D` and `I` on the following two lines. Then, if we find an `I` then eat it and match the characters to the next `I` and `D`, otherwise just match characters to the next `D` or the end of the line.

```
L$`
$4$5

```

List captures 4 and 5 from each match; 4 is the capture between two `I`s while 5 is the capture between two `D`s.

# Answer
> 3 votes
# Powershell, 71 bytes

```
param($d,$i,$s)$s-split{(1-($script:a+=$i-ceq$_)%2)*($d-ceq$_)}|% *m $i

```

Less golfed test script:

```
$f = {

param($d,$i,$s)
$s-split{
    $script:a+=$i-ceq$_
    (1-$a%2)-and($d-ceq$_)
}|% Trim $i

}

@(
    ,(',','"',
    '',
    '')

    ,(',','"',
    'a,"b,c",d,,e,"",f',
    'a', 'b,c', 'd', '', 'e', '', 'f')

    ,(',','"',
    '11020199,"Abc ",aduz,,444,bieb,dc,2 ,2222.00,whatever 5dc,222.22,22.00,"98,00","12,000,000",21-09-2018, 06:00,",-,"',
    '11020199', 'Abc ', 'aduz', '', '444', 'bieb', 'dc', '2 ', '2222.00', 'whatever 5dc', '222.22', '22.00', '98,00', '12,000,000', '21-09-2018', ' 06:00', ',-,')

    ,(' ',',',
    'this is a test , to see if you understand it, or not , hmmm, I think I have too many commas , or not , perhaps..',
    'this', 'is', 'a', 'test', ' to see if you understand it', 'or', 'not', ' hmmm', 'I', 'think', 'I', 'have', 'too', 'many', 'commas', ' or not ', 'perhaps..')

    ,('x','y',
    'contains no lowercase X nor Y',
    'contains no lowercase X nor Y')

    ,('1','3',
    '3589841973169139975105820974944592078316406286208948254211370679314',
    '58984197', '69', '9975105820974944592078', '64062862089482542', '', '70679', '4')

    ,(' ','S',
    'regular split on spaces',
    'regular', 'split', 'on', 'spaces')

) | % {
    $d,$i,$s,$expected = $_
    $result = &$f $d $i $s
    "$("$result"-eq"$expected"): $result"
}

```

Output:

```
True:
True: a b,c d  e  f
True: 11020199 Abc  aduz  444 bieb dc 2  2222.00 whatever 5dc 222.22 22.00 98,00 12,000,000 21-09-2018  06:00 ,-,
True: this is a test  to see if you understand it or not  hmmm I think I have too many commas  or not  perhaps..
True: contains no lowercase X nor Y
True: 58984197 69 9975105820974944592078 64062862089482542  70679 4
True: regular split on spaces

```

Explanation:

# Answer
> 2 votes
# Pip `-n`, ~~29~~ 24 bytes

```
cR Xa[na]@(bN{$`})^n||:b

```

Takes inputs as command-line arguments. Try it online!

Strategy: outside `I` pairs, replace `D` with newline (since we're guaranteed that newlines won't appear in the string). Then split on newline and strip `I`.

# Answer
> 2 votes
# SNOBOL4 (CSNOBOL4), 109 bytes

```
	D =INPUT
	I =INPUT
	S =INPUT
S	S (I ARB . OUTPUT I | ARB . OUTPUT) (D | RPOS(0)) REM . S	DIFFER(S)	:S(S)
END

```

Try it online!

Suppose that `D =','` and `I ='"'`. Then the pattern `(I ARB . OUTPUT I | ARB . OUTPUT) (D | RPOS(0))` matches strings that look like `".*"` or `.*` followed either by `,` or by the end of the string, and OUTPUTs the arbitrary (`.*`) characters, setting the unmatched REMainder to `S` and iterating so long as `S` is not empty.

# Answer
> 2 votes
# Jelly,  ~~20~~  18 bytes

```
;`j⁵œṣ⁴œṣḊṖYʋ€Ðo³Y

```

A full program taking the three arguments `D`, `I`, `S` which prints each item on a line.

**Try it online!** (Footer joins with newlines)

### How?

Surround with an extra `D` on each side, split at `I`s, split the odd-indexed items at `D`s then remove their heads and tails and join them with newlines, finally join the result with newlines.

# Answer
> 2 votes
# PHP, 50 bytes

```
function q($D,$I,$S){return str_getcsv($S,$D,$I);}

```

Try it online! Uses a built-in function.

If rearranging the inputs is allowed (`(S,D,I)` so it matches the `str_getcsv` signature), I have a 44 byte version.

---
Tags: code-golf, string
---


title: Seeking Substantial Subcollections

text:
# Question
Title: Seeking Substantial Subcollections
*(thanks to @JonathanFrech for the title)*

## Challenge

Write a program or function that, given a collection of positive integers \\$S\\$ and a positive integer \\$n\\$, finds as many non-overlapping subcollections \\$T\_1, T\_2, ..., T\_k\\$ of \\$S\\$ as possible, such that the sum of every \\$T\_m\\$ is equal to \\$n\\$.

### Example

Given \\$S=\lbrace1,1,2,2,3,3,3,5,6,8\rbrace\\$ and \\$n=6\\$, you could take the following subcollections to get \\$k=3\\$:

* \\$T\_1=\lbrace1,1,2,2\rbrace\\$
* \\$T\_2=\lbrace3,3\rbrace\\$
* \\$T\_3=\lbrace6\rbrace\\$

And the remaining elements \\$\lbrace3,5,8\rbrace\\$ are not used. However, there is a way to get \\$k=4\\$ separate subcollections:

* \\$T\_1=\lbrace1,2,3\rbrace\\$
* \\$T\_2=\lbrace1,5\rbrace\\$
* \\$T\_3=\lbrace3,3\rbrace\\$
* \\$T\_4=\lbrace6\rbrace\\$

This leaves \\$\lbrace2,8\rbrace\\$ unused. There is no way to do this with 5 subcollections1, so \\$k=4\\$ for this example.

### Input

Input will be a collection of positive integers \\$S\\$, and a positive integer \\$n\\$. \\$S\\$ may be taken in any reasonable format: a comma- or newline-separated string, an actual array/list, etc. You may assume that \\$S\\$ is sorted (if your input format has a defined order).

### Output

The output may be either:

1. the maximal number of subcollections \\$k\\$; or
2. any collection which has \\$k\\$ items (e.g., the list of subcollections \\$T\\$ itself), in any reasonable format.

Note that there is not guaranteed to be any subcollections with sum \\$n\\$ (i.e. some inputs will output `0`, `[]`, etc.)

### Test cases

```
n, S -> k
1, [1] -> 1
1, [2] -> 0
2, [1] -> 0
1, [1, 1] -> 2
2, [1, 1, 1] -> 1
3, [1, 1, 2, 2] -> 2
9, [1, 1, 3, 3, 5, 5, 7] -> 2
9, [1, 1, 3, 3, 5, 7, 7] -> 1
8, [1, 1, 2, 3, 4, 6, 6, 6] -> 2
6, [1, 1, 2, 2, 3, 3, 3, 5, 6, 8] -> 4
13, [2, 2, 2, 2, 3, 3, 4, 5, 5, 6, 8, 9, 9, 11, 12] -> 5
22, [1, 1, 2, 3, 3, 3, 3, 3, 4, 4, 4, 5, 6, 6, 7, 7, 7, 8, 9, 9, 10, 13, 14, 14, 17, 18, 18, 21] -> 10

```

### Scoring

This is , so **the shortest program in bytes in each language wins**. Good luck!

---

1. Mini-proof: the \\$8\\$ is obviously useless, but when you remove it, the total sum of \\$S\\$ becomes \\$26\\$; therefore, it can only contain up to \\$4\\$ non-overlapping subcollections whose sums are \\$6\\$.

# Answer
# Jelly,  ~~17 11~~  10 bytes

-1 Thanks to Dennis (use count to remove the need to tie atoms together with any quick)

```
Œ!ŒṖ€§Ẏċ€Ṁ

```

A dyadic link accepting a list and an integer which yields the maximal count, \\$k\\$.

**Try it online!** Or see the test-suite -- it's too slow for the larger test cases :(

### How?

```
Œ!ŒṖ€§Ẏċ€Ṁ - Link: list L, integer I
Œ!         - all permutations
  ŒṖ€      - for €ach: all partitions (all ways to slice up each permutation)
     §     - sum each (vectorises at depth 1, so this gets the sums of the parts of
           -           each of the partitions for each permutation)
      Ẏ    - tighten  (to get a list of the sums of the parts of each possible partition)
       ċ€  - for €ach count occurrences of I
         Ṁ - maximum

```
> 3 votes

# Answer
# Jelly, 17 bytes

```
Œ!ŒṖ€ẎŒP€Ẏ§;EɗƇẈṀ

```

Try it online!

Outputs \\$k\\$ if there is a \\$T\\$, \\$0\\$ otherwise. Very slow.
> 1 votes

# Answer
# 05AB1E, ~~9~~ 8 bytes

```
œ€.œOQOZ

```

Port of *@JonathanAllan*'s Jelly answer.

Try it online. NOTE: Extremely slow, so times out for most test cases beyond the size of 6..

**Explanation:**

```
œ           # All permutations of the (implicit) input-list
 €.œ        # Take all partitions of each permutation
    O       # Sum each
     Q      # Check for each if it's equal to the (implicit) integer-input
      O     # Then sum each
       Z    # And take the maximum (implicitly flattens the list of lists)
            # (and output implicitly)

```
> 1 votes

# Answer
# JavaScript (Node.js), 115 bytes

```
k=>f=([i,...s])=>i?Math.max(...[i,...s].map((_,j)=>(e[j]=~~e[j]+i,_=f(s),e[j]-=i,_))):e.filter(_=>_==k).length;e=[]

```

Try it online!
> 0 votes

---
Tags: code-golf, number, combinatorics
---


title: Minecraft Language Files Updater

text:
# Question
Title: Minecraft Language Files Updater
In 1.13, Minecraft language files were switched from being a simple multi-line key=value format to JSON.

# Challenge

Write a program converting from the original format returning a JSON string. Input can be taken using any standard input method, output must be json from any standard output method

The original format contains lines with key=value pairs, for example

```
tile.dirt.name=Dirt
advMode.nearestPlayer=Use "@p" to target nearest player

build.tooHigh=Height limit for building is %s blocks

```

Should be converted to one large JSON object with key=value

```
{
    "tile.dirt.name": "Dirt",
    "advMode.nearestPlayer": "Use \"@p\" to target nearest player",
    "build.tooHigh": "Height limit for building is %s blocks"
}

```

## Some details

* Any valid JSON is allowed as long as it contains only the correct key/value pairs. Trailing commas are allowed because Minecraft allows them.
* The only things that must be escaped are quotes. (No newlines, backslashes, or other json-breaking things existed in the language file prior to 1.13)
* Empty lines should be ignored
* Lines contain exactly one equals

# Test Cases

Input:

```
tile.dirt.name=Dirt
advMode.nearestPlayer=Use "@p" to target nearest player

build.tooHigh=Height limit for building is %s blocks

```

Output:

```
{
    "tile.dirt.name": "Dirt",
    "advMode.nearestPlayer": "Use \"@p\" to target nearest player",
    "build.tooHigh": "Height limit for building is %s blocks"
}

```

Input:

```
translation.test.none=Hello, world!
translation.test.complex=Prefix, %s%2$s again %s and %1$s lastly %s and also %1$s again!
translation.test.escape=%%s %%%s %%%%s %%%%%s
translation.test.invalid=hi %
translation.test.invalid2=hi %  s
translation.test.args=%s %s
translation.test.world=world

```

Output:

```
{
  "translation.test.none": "Hello, world!",
  "translation.test.complex": "Prefix, %s%2$s again %s and %1$s lastly %s and also %1$s again!",
  "translation.test.escape": "%%s %%%s %%%%s %%%%%s",
  "translation.test.invalid": "hi %",
  "translation.test.invalid2": "hi %  s",
  "translation.test.args": "%s %s",
  "translation.test.world": "world",
}

```

Input:

```
stat.mineBlock=%1$s Mined
stat.craftItem=%1$s Crafted
stat.useItem=%1$s Used
stat.breakItem=%1$s Depleted

```

Output:

```
{
    "stat.mineBlock": "%1$s Mined",
    "stat.craftItem": "%1$s Crafted",
    "stat.useItem": "%1$s Used",
    "stat.breakItem": "%1$s Depleted"
}

```

# Answer
# Python 3, ~~91~~ 77 bytes

*-14 Bytes thanks to OMᗺ*

I thought that the printout of a Python dictionary would be close enough to JSON to make it a very competitive language for this challenge. However, the string representation of python dictionaries is different enough from JSON that I had better luck using python's built-in JSON library. I'll bet this can be done more succinctly in JavaScript.

```
import json
f=lambda x:json.dumps(dict(i.split("=")for i in x.split("\n")if i))

```

Try it Online!

---

Edit:

# Bash + Sed, ~~68~~ 63 bytes

*Bug fix thanks to OMᗺ and Night 2*
*-5 Bytes thanks to OMᗺ*

I realized that it might be more byte efficient to directly convert the text to JSON without bundling it in an object, as was my approach for the python solution. Per byte, sed is the most powerful language for regex replacement that I know of.

```
echo {`echo "$1"|sed 's/"/\\\"/g;s/\(.*\)=\(.*\)/"\1":"\2",/'`}

```

Try it Online!

## Explanation

```
echo {`                                  #  prints the leading curly brace
       echo "$1"|sed                     # feeds the input into sed
       's/"/\\"/g;                       # replaces " with \"
       s/\(.*\)=\(.*\)/"\1":"\2",/'      # surrounds the left and right hand sides of the equals with quotes and joins them with a colon
`}                                       # prints the closing curly brace

```
> 4 votes

# Answer
# Vim, 44 bytes

```
O{*<Esc>*:%s/"/\\"/g|%s/\v(.*)\=(.*)/"\1":"\2",
o}

```

Explanation:

```
O{*<Esc>*                                           Prepend {
       :%s/"/\\"/g                                Escape all "
                  |%s/\v(.*)\=(.*)/"\1":"\2",     Json-ify lines
o}                                                Append }

```
> 4 votes

# Answer
# Rust, 150 bytes

```
|s:String|s.replace('"',"\\\"").split('\n').filter(|l|l.len()>0).map(|l|format!("\"")+&l.replace('=',"\":\"")+"\",").fold(format!("{{"),|r,n|r+&n)+"}"

```

Try it online!

Is it longer than Java?
> 3 votes

# Answer
# Retina 0.8.2, 35 bytes

```
"
\"
=
": "
G`.
.+
    "$&",
^
{¶
$
¶}

```

Try it online! Would be 34 bytes in Retina 1 as you can use `L$`.+` instead of `G`.` and `.+`. Explanation:

```
"
\"

```

Escape the quotes.

```
=
": "

```

Fix up the key/value separator. (If the value might contain a `=`, use `1`=` at a cost of 2 bytes.)

```
G`.

```

Remove empty lines.

```
.+
    "$&",

```

Wrap each line in quotes. (The inner quotes were added earlier.)

```
^
{¶
$
¶}

```

Wrap the entire output in `{}`s.
> 2 votes

# Answer
# Perl 5 `-nl -M5.010`, ~~58~~ 54 bytes

```
BEGIN{say'{'}s'"'\"'g;/=/&&say qq|"$`": "$'",|}{say'}'

```

Try it online!

---

58 byte version:

```
BEGIN{say'{'}s'"'\"'g;s/(.*)=(.*)/"$1": "$2",/;END{say'}'}

```

Try it online!
> 2 votes

# Answer
# Husk, 22 bytes

String manipulation is not really Husk's strength, but it did pretty well:

```
`J"{}"J',mȯJ':msx'=fI¶

```

Try it online!

```
                      ¶  -- split on newlines
                    fI   -- filter by identity (ie. remove empty strings)
         m(        )     -- with each line
                x'=      -- | split on '='
              ms         -- | show each (ie. enclose in quotes and escape quotes)
           J':           -- | join with ':'
      J',                -- join these with ','
`J"{}"                   -- join the string "{}" with the result

```
> 2 votes

# Answer
# JavaScript, ~~66~~ ~~63~~ 62 bytes

```
s=>JSON.stringify(o=/(.+)=(.+)/g,s.replace(o,(_,a,b)=>o[a]=b))

```

```
f=
s=>JSON.stringify(o=/(.+)=(.+)/g,s.replace(o,(_,a,b)=>o[a]=b))

console.log(
  f(`tile.dirt.name=Dirt
advMode.nearestPlayer=Use "@p" to target nearest player

build.tooHigh=Height limit for building is %s blocks`)
)
```

*-3 bytes thanks to @redundancy*

*-1 byte thanks to @l4m2*
> 2 votes

# Answer
# Haskell, ~~75~~ 71 bytes

<sup>-4 bytes thanks to Laikoni (using do-notation over list-comprehension)!</sup>

Works with multiple `=` on one line:

```
f s='{':do{(a,_:b)<-span(/='=')<$>lines s;show a++':':show b++","}++"}"

```

Try it online!

## Explanation

The term `span(/='=')<$>lines s` splits the string on the first `=`, leaving us with `("<initial part>","=<remaining line>")`. Doing a pattern-match `(a,_:b)` ensures that the line was not empty and at the same time removes the leading `=`.

Now we only need to `show` both `a` and `b` (enclosing it in quotes and escaping quotes), do some formatting (`:` and `,` characters) and finally enclose it in `{}`.
> 2 votes

# Answer
# Ruby, 56 bytes

```
->x{x.split(?\n).map{|i|i.split(?=)}.to_h.to_json}

```

+6 bytes for `-rjson` interpreter flag.

Try it online!
> 2 votes

# Answer
# C (gcc), 243 219 bytes

Thanks to ceilingcat for the suggestion.

I decided to use a state machine to handle the three cases (newline, key, value) and it turned out pretty well. Also, I got to abuse the fall-through feature of `switch` and the macro stringizing operator!

Although the challenge didn't require it, I also escaped the `\` character per the JSON spec. If that character will never be in the input, then `&&c-92` can be removed for 5 more bytes.

```
#define p(s)printf(#s,c)
#define a(i)case i:
c,s;f(){for(p({);(c=getchar())>0;)switch(s){a(0)if(c<11)break;s++,p(\42);a(1)c==61?s++,p(":"):p(%c);break;a(2)c-34&&c-92?c==10?p(\42\54),s=0:p(%c):p(\\%c);}s-2||p(\42);p(});}

```

Try it online!

---

## Original submission: 243 bytes

The original submission kept unneeded spacing as in the provided JSON examples.

```
#define p(s)printf(s,c)
#define a(i)case i:
c,s;f(){for(p("{\n");(c=getchar())>0;)switch(s){a(0)if(c<11)break;s++,p("  \"");a(1)c==61?s++,p("\": \""):p("%c");break;a(2)c-34&&c-39?c==10?p("\",\n"),s=0:p("%c"):p("\\%c");}s==2&&p("\"\n");p("}");}

```

Try it online!
> 2 votes

# Answer
# Retina 0.8.2, 43 bytes

```
¶¶
¶
"
\"
=
": "
m`$|^
"
m`^

$
¶}
^
{¶

```

Try it online!
> 1 votes

# Answer
# JavaScript (ES6), 66 bytes

```
s=>`{${s.replace(/"/g,'\\"').replace(/(.*)=(.*)/g,'"$1":"$2",')}}`

```

Assumes there's only one `=` per line

## Testing snippet

```
f=s=>`{${s.replace(/"/g,'\\"').replace(/(.*)=(.*)/g,'"$1":"$2",')}}`
```

```
<textarea id="i" onkeyup="o.innerText=f(i.value)"></textarea><pre id="o">
```
> 1 votes

# Answer
# Perl 6, 48 bytes

```
{to-json %(.lines.grep(?*)>>.split("=",2).flat)}

```

*2 bytes less if we can assume exactly 1 equals sign on a non-empty line.*

Try it online!

Ungolfed:

```
{                   # An anonymous block, taking 1 string which ends in $_.
    to-json         # Convert a Perl 6 number, string, list or hash to JSON and return it.
    %(              # Force to hash (dictionary)
        .lines      # Break $_ (implicitly assumed) into a list of lines.
        .grep(?*)   # Pick only those that are True (non-empty).
        >>.         # For each element in the list, call the following method ...
        split("=",2) # ... split the string at =, making at most 2 chunks.
        .flat       # That gives a list of 2-element lists. Flatten it.
    )               # List is converted into the hash like this: { first element => second element, third => fourth, ... }
}                   # Implicitly return

```

By the way, the `to-json` routine is deprecated, as the compiler will tell you, but who cares.
> 1 votes

# Answer
# Python 2, 81 bytes

```
lambda s:'{'+re.sub(r'(.*)=(.*)',r'"\1":"\2",',re.sub('"',r'\"',s))+'}'
import re

```

Try it online!
> 1 votes

# Answer
## Ruby, 59 + 5 = 64

Needs `-rjson` (+5)

```
->c{Hash[*c.split(?\n).map{|l|l.split ?=}.flatten].to_json}

```

Explanation:

```
->c{                                                      } # anonymous function with param c
    Hash[*                                       ]          # converts ["a", "b", "c", "d"] into {"a": "b", "c": "d"}
          c.split(?\n)                                      # splits c into lines
                      .map{|l|          }                   # map lines so each element represents
                              l.split ?=                    # an array of itself but split by =
                                         .flatten           # merges 2d array to 1d (also gets rid of empty elements for newlines
                                                  .to_json  # converts hash to json

```
> 1 votes

# Answer
# , 30 bytes

```
O{␛Í"/\\"
ggòeÉ"vyf=Plp$pa,òo}

```

Expects one input at a time. The TIO snippet runs all given test cases as a single input.

I'm new to V's extended mappings, so tips are always welcome!

Try it online!

## Explanation

```
O{␛                  # insert { on a new line above
   Í                 # global substitution across all lines
    "/\\"            #   " => \"
gg                   # go to first line
  ò                  # recursively...
   e                 #   forward to end of word; if at end of line, applies to next word below
    É"               #   prepend " to first non-whitespace char
      vy             #   copy current character (i.e. ")
        f=Plp        #   paste " before and after the next =
             $pa,    #   paste " at end of line and append ,
                 ò   # ...end
                  o} # insert } on a new line below

```
> 1 votes

# Answer
# C (gcc), ~~172~~ 170 bytes

```
#define p(s)printf(#s,c)
c,s;f(){for(p({);read(0,&c,1);)s-2?c>10|s&&(s||(s+=p(\42)),c==61?s++,p(":"):p(%c)):c-34&&c-92?c==10?s=!p(\42\54):p(%c):p(\\%c);s-2||p(\42);p(});}

```

Try it online!

Based on @ErikF's implementation but without `switch/case`.

Slightly ungolfed version

```
#define p(s)printf(#s,c)
c,s;
f(){
 for(p({);read(0,&c,1);)
  s-2?
   c>10|s&&(
    s||
     (s+=p(\42)),
    c==61?
     s++,
     p(":")
    :
     p(%c)
   )
  :
   c-34&&c-92?
    c==10?
     s=!p(\42\54)
    :
     p(%c)
   :
    p(\\%c);
 s-2||p(\42);
 p(});
}

```
> 1 votes

# Answer
# R, 118 bytes

```
function(s){cat(paste("{",gsub("(.*)=(.*)","\"\\1\":\"\\2\",",gsub("\"","\\\\\"",gsub("\n{2,}","\n",s)),perl=T),"}"))}

```

Try it online!
> 1 votes

# Answer
# C (gcc), 119 bytes

```
#define p(s)printf(#s,c)
s;f(c){for(p({);~(c=getchar())|s;)c<11?s=s&&!p(",�"):c-61?s++||p(\42),p(\\u%04x):p(":");p(});}

```

Try it online!
> 1 votes

# Answer
# PHP, 87 bytes

```
preg_match_all("/^(.*)=(.*)$/m",$argn,$m);echo json_encode(array_combine($m[1],$m[2]));

```

Run as pipe with `-nR` or try it online.

Insert `\s` before `$/m` for Windows linebreaks; `\s*` if linebreaks are uncertain.
Insert `U` after `$/m` if values contain `=`.
> 1 votes

# Answer
# Dart, ~~142~~ ~~114~~ 108 bytes

```
f(s)=>"""{${s.replaceAll('"','\\"').replaceAllMapped(RegExp(r'(.*)=(.*)'),(m)=>'"${m[1]}":"${m[2]}",')}}""";

```

Try it online!

- -28 bytes by getting rid of the json.encode function and using regular string building
- -6 bytes by removing the 'new' keyword and a few spaces
> 1 votes

---
Tags: code-golf, game, json
---


title: Smoothing a pair of arrays

text:
# Question
Title: Smoothing a pair of arrays
# Input

Two lists with binary values `(list_a, list_b)` of equal length=\>3.

# Output

Two lists with binary values `(smoothed_a, smoothed_b)` with minimal Forward Difference while keeping the same sum before and after processing `sum(list_a) + sum(list_b) == sum(smoothed_a) + sum(smoothed_b)`.

**Forward Difference** being the absolute difference between items. For example:

* `[0, 1, 0]` would be `sum(abs([1, -1])) => 2`
* `[1, 1, 1]` would be `sum(abs([0, 0])) => 0`

# Illustrative test cases

Formatted as `(list_a, list_b) => (smoothed_a, smoothed_b)`

```
([0, 0, 1, 0, 0],
 [1, 1, 0, 1, 1])
=>
([0, 0, 0, 0, 0],
 [1, 1, 1, 1, 1])

```

The sum of both arrays pairs is 5. The forward difference was minimized to 0.

```
([1, 0, 1, 0, 1],
 [0, 0, 0, 1, 0])
=>
([0, 1, 1, 1, 1],
 [0, 0, 0, 0, 0])

```

The sum of both arrays pairs is 4. The forward difference was minimized to 1.

# Test cases

Formatted as `(list_a, list_b): forward_diff => (smoothed_a, smoothed_b): min_diff` where `(smoothed_a, smoothed_b)` are potential solutions.

```
([0, 0, 1],
 [0, 1, 0]): 3
([0, 0, 0],
 [0, 1, 1]): 1

([1, 1, 1],
 [0, 0, 0]): 0
([1, 1, 1],
 [0, 0, 0]): 0

([0, 1, 0],
 [1, 0, 1]): 4
([0, 0, 0],
 [1, 1, 1]): 0

([1, 1, 1, 1],
 [0, 0, 0, 0]): 0
([1, 1, 1, 1],
 [0, 0, 0, 0]): 0

([1, 0, 1, 1],
 [0, 0, 0, 1]): 3
([1, 1, 1, 1],
 [0, 0, 0, 0]): 0

([1, 0, 0, 1],
 [0, 0, 0, 1]): 2
([1, 1, 1, 0],
 [0, 0, 0, 0]): 1

([1, 1, 0, 1],
 [1, 0, 1, 0]): 3
([1, 1, 1, 1],
 [1, 0, 0, 0]): 1

```

# Answer
# Jelly, 3 bytes

```
FṢṁ

```

Try it online!

Explanation:

* **F**latten the list
* ort the flattened list
* old the sorted flatten list in the shape of the input.
> 5 votes

# Answer
# Retina, 4 bytes

```
O`\d

```

My shortest Retina answer thus far.

Try it online or verify all test cases.

**Explanation:**

Sorts all digits in the input, and leaves every other character unchanged (including their positions).
> 3 votes

# Answer
# Python 2, 51 bytes

```
def f(a,b):s=sorted(a+b);l=len(a);print s[:l],s[l:]

```

Try it online!

Function that prints to STDOUT.
> 1 votes

# Answer
# Husk, 3 bytes

```
½OΣ

```

Try it online!

```
½OΣ – Full program. Takes a list of two lists from the first CLA, outputs to STDOUT.
  Σ – Flatten (i.e. concatenate the contents of the 2 lists together).
 O  – Sort.
½   – Divide list in two halves (i.e. partition it into two equal-length sublists).

```
> 1 votes

# Answer
# J, 7 bytes

```
$$/:~@,

```

## explanation

```
$            NB. use the input shape
  $          NB. to shape the result of...
    /:~      NB. sorting the input
        @,   NB. after flattening it

```

Try it online!
> 1 votes

# Answer
# C gcc compile flag 64bit, 31 bytes by Rogem

```
-Df(a,n)=qsort(a,n+n,4,"\x8b\x07+\x06\xc3")

```

Try it online!

# C gcc 32bit, 37 bytes

```
f(a,n){qsort(a,n+n,4,"YXZ\x8B\x00+\x02QQQ\xC3");}
struct {
    int a[5], b[5];
} test;
int main() {
    test.a[0] = test.a[2] = test.b[1] = 1;
    f(&test, 5);
    printf ("%d%d%d%d%d\n", test.a[0], test.a[1], test.a[2], test.a[3], test.a[4]);
    printf ("%d%d%d%d%d\n", test.b[0], test.b[1], test.b[2], test.b[3], test.b[4]);
    return 0;
}

```

Written non-ASCII to `\x??` so se won't eat
> 0 votes

# Answer
# 05AB1E, 4 bytes

```
˜{2ä

```

Try it online or verify all test cases.

**Explanation:**

```
˜       # Flatten the (implicit) input list of lists
 {      # Sort it
  2ä    # Split it into two equal-sized lists (and output implicitly)

```
> 0 votes

# Answer
# Charcoal, 14 bytes

```
⪪⭆⊗Ｌθ‹ι№⁺θη¹Ｌθ

```

Try it online! Link is to verbose version of code. Explanation: Charcoal doesn't have a sort atom, but all we need to do is to put all the `1`s at the front of the list, which is done by counting them and then setting that many list entries to `1` and the remaining ones to `0`:

```
    θ           First input
   Ｌ            Length
  ⊗             Doubled
 ⭆              Map over implicit range and join
         θ      First input
          η     Second input
        ⁺       Concatenate
           ¹    Literal 1
       №        Count matches
      ι         Current index
     ‹          Less than
             θ  First input
            Ｌ   Length
⪪               Split into strings of that length
                Implcitly print each string on its own line

```
> 0 votes

# Answer
# , 57 bytes

```
function(a,b,s=1:sum(a|1),x=sort(c(a,b)))list(x[s],x[-s])

```

Try it online!
> 0 votes

# Answer
# Scala, 60 bytes

```
def^(a:List[Int],b:List[Int])=(a:::b).sorted.splitAt(a.size)

```

Try it online!
> 0 votes

---
Tags: code-golf, array
---


title: Simulate an NFA

text:
# Question
Title: Simulate an NFA
A *nondeterministic finite automaton* is a finite state machine where a tuple \\$(state,symbol)\\$ is mapped to multiple states. Ie. we replace the usual \\$\delta : Q \times \Sigma \to Q\ \\$ transition function of a DFA with another function \\$\Delta : Q \times \Sigma \to \mathcal{P}(Q)\\$.

If you know what an NFA is you might want to skip the next section.

### Formal Definition

An NFA is uniquely described by

* \\$Q\\$ a finite set of states
* \\$\Sigma\\$ a finite set of symbols
* \\$\Delta : Q \times \Sigma \to \mathcal{P}(Q)\\$ the transition function
* \\$q\_0 \in Q\\$ the initial state
* \\$F \subseteq Q\\$ a set of final states

The machine starts out in \\$q\_0\\$ and reads a finite string of symbols \\$w \in \Sigma^\*\\$, for each symbol it will simultaneously apply the transition function function with a current state and add each new set of states to the set of current states.

## Challenge

For this challenge we will ignore \\$F\ \\$ to simplify it, furthermore the alphabet will always be the (lower-case) letters \\$\texttt{a}\ \\$ to \\$\texttt{z}\ \\$ and the set of states will be \\$\\{0 \dots N\\}\\$ for some non-negative integer \\$N\\$. The initial state will always be \\$0\\$.

Given a word \\$w \in \\{\texttt{a}\dots\texttt{z}\\}^\*\\$ and a description of the NFA, your task is to determine all the final states.

### Example

Consider the string \\$\texttt{abaab}\\$ and the following description:

```
state, symbol, new-states
0, 'a', [1]
1, 'a', [0]
1, 'b', [1,2]

```

The machine will start in \\$q\_0 = 0\\$:

1. read an \\$\texttt{a}\\$: new states \\$\\{1\\}\\$
2. read a \\$\texttt{b}\\$: new states \\$\\{1,2\\}\\$
3. read an \\$\texttt{a}\\$: new states \\$\\{0\\}\\$
4. read an \\$\texttt{a}\\$: new states \\$\\{1\\}\\$
5. read a \\$\texttt{b}\\$: new states \\$\\{1,2\\}\\$

So the final states and thus the output would be \\$\\{1,2\\}\\$.

**Note:** In step *(2)* the transition of state \\$2\\$ maps to \\$\emptyset\\$ as the description only includes transitions to non-empty sets.

## Rules

The input will consist of a string and some kind of description of the NFA (without \\$\epsilon\\$-transitions):

* the input string will always be element of \\$\\{\texttt{a}\dots\texttt{z}\\}^\*\\$
* valid inputs (not limited to):
    + list/array of tuples/lists
    + new-line separated input
* the description of the NFA will only contain transitions with non-empty sets as result
    + you may abbreviate rules with the same characters if their result is the same (eg. rules `0,'a',[1,2]` and `0,'b',[1,2]` could be abbreviated with `0,"ab",[1,2]`
    + you may take each rule separate (eg. rule `0,'a',[1,2]` can be `0,'a',[1]` and `0,'a',[2]`)
* you may choose upper-case letters if you want
* you may take the number of states as input
* you may assume some kind of ordering of the inputs (eg. ordered by state or symbols)

The output will be a list/set/new-line separated output etc. of the final states

* order doesn't matter
* no duplicates (as it's a set)

### Test cases

These examples will be in the format `description word -> states` where `description` is a list of tuples `(state,symbol,new-states)`:

```
[]  "x" -> []
[]  "" -> [0]
[(0,'a',[1]),(1,'a',[0]),(1,'b',[1,2])]  "abaab" -> [1,2]
[(0,'a',[1]),(1,'a',[0]),(1,'b',[1,2])]  "abc" -> []
[(0,'p',[0,1]),(0,'g',[2]),(1,'c',[1]),(1,'g',[4]),(1,'p',[2]),(2,'c',[0])]  "ppcg" -> [2,4]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])]  "foobar" -> [0,4]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])]  "fooooooobar" -> [0,4]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])]  "fobarfo" -> [1,2]
[(0,'f',[1]),(1,'o',[1,2]),(2,'b',[3]),(3,'a',[4]),(4,'r',[0,4])]  "foobarrf" -> [1]
[(0,'d',[1,2]),(1,'u',[2]),(2,'u',[2,3]),(2,'p',[3]),(3,'p',[3])]  "dup" -> [3]
[(0,'a',[0,2]),(0,'b',[3]),(1,'a',[1]),(1,'b',[1]),(2,'b',[1,4]),(4,'b',[2])]  "aab" -> [3,1,4]
[(0,'a',[0,2]),(0,'b',[3]),(1,'a',[1]),(1,'b',[1]),(2,'b',[1,4]),(4,'b',[2])]  "abb" -> [1,2]

```

# Answer
> 7 votes
# Haskell, 66 bytes

```
import Data.List
f d=foldl(\s c->nub[r|(y,r)<-d,g<-s,(g,c)==y])[0]

```

Try it online!

# Answer
> 4 votes
# Brachylog, 42 bytes

```
,0{hẸ&t|∋₁B∋IhJ&tJ&hhC∧I∋₁C∧It∋S&hb;B,S↰}ᵘ

```

input as \[string, nfa\] where nfa is a list of state transitions \[ initial state, letter, new states as list \]

# Explanation

```
,0                                              # Append 0 to the input (initial state)
  {                                      }ᵘ     # Find all unique outputs
   h                                            # if first element (string)
    Ẹ                                           #   is empty
     &t                                         #   then: return last element (current state)
       |                                        #   else:
        ∋₁B                                     #       save the state transitions in "B"
           ∋I                                   #       take one of these transitions, save in "I"
             hJ                                 #       take the initial state requirement, store in "J"
               &tJ                              #       make sure "J" is actually the current state
                  &hhC                          #       Save first char of string in C
                      ∧I∋₁C                     #       make sure the char requirement for the state transition is the current char
                           ∧It∋S                #       Make "S" equal to one of the new states
                                &hb             #       Behead the string (remove first char)
                                   ;B,S         #       Add B (the state transitions) and S (the new state)
                                       ↰        #       recur this function

```

Try it online!

# Answer
> 4 votes
# Brachylog v2, 31 bytes

```
{b,Ȯ,Ȯ\c↔,0↔ġ₃kH&hg;Hz{∋ᵈ}ᵐtt}ᵘ

```

Try it online! (or with a more complex example)

Brachylog is really good at this sort of problem, and really bad at problems that require two separate inputs and an output. Almost all of this program is just plumbing.

Input format is a list containing two elements: the first is the list of state transitions (`[oldState, symbol, newState]`), and the second is the list of symbols. I originally planned this program to work with character codes for symbols (because Brachylog's string handling can be a bit weird sometimes), but it turns out that characters work too (although you have to write the input string as a list of characters, not as a string). If a state-symbol pair can transition to multiple different states, you write multiple transitions to deal with that.

## Explanation

```
{b,Ȯ,Ȯ\c↔,0↔ġ₃kH&hg;Hz{∋ᵈ}ᵐtt}ᵘ
{                            }ᵘ   Find all distinct outputs that can result from:
 b                                  taking the input minus its first element,
  ,Ȯ                                appending a singleton list (i.e. an element)
    ,Ȯ                              then appending that same element again
      \                             and transposing;
       c                            then concatenating the resulting lists,
        ↔,0↔                        prepending a 0,
            ġ₃                      grouping into blocks of 3 elements
              k                       (and discarding the last, incomplete, block),
               H&                   storing that while we
                 h                  take the first input element,
                  g  z              pair a copy of it with each element of
                   ;H                 the stored value,
                      {  }ᵐ         assert that for each resulting element
                       ∋ᵈ             its first element contains the second,
                        ᵈ ᵐ           returning the list of second elements,
                            t       then taking the last element of
                           t          the last element.

```

It's probably easier to follow this by looking at what some partial versions of the program would produce. Using the following input each time:

```
[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]

```

we can observe the outputs of some prefixes of this program:

```
[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,Ȯ,Ȯ
[[97,98,97,97,98],L,L]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,Ȯ,Ȯ\
[[97,A,A],[98,B,B],[97,C,C],[97,D,D],[98,E,E]]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,Ȯ,Ȯ\c↔,0↔
[0,97,A,A,98,B,B,97,C,C,97,D,D,98,E,E]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,Ȯ,Ȯ\c↔,0↔ġ₃k
[[0,97,A],[A,98,B],[B,97,C],[C,97,D],[D,98,E]]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,Ȯ,Ȯ\c↔,0↔ġ₃kH&hg;Hz
[[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[0,97,A]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[A,98,B]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[B,97,C]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[C,97,D]],
 [[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[D,98,E]]]

[[[0,97,1],[1,97,0],[1,98,1],[1,98,2]],[97,98,97,97,98]]b,Ȯ,Ȯ\c↔,0↔ġ₃kH&hg;Hz{∋ᵈ}ᵐ
e.g. [[0,97,1],[1,98,1],[1,97,0],[0,97,1],[1,98,1]]

```

For the first example here, `L` is initially an unknown element, but when we transpose it via `\`, Brachylog realises that the only possibility is a list with the same length as the input. The last example here is nondeterministic; we're modelling nondeterminism in the NFA using the nondeterminism in Brachylog itself.

## Possible improvements

Some of the syntax here, like `↔,0↔` and especially the mess with `H&hg;Hz{…ᵈ}ᵐ`, is fairly clunky. It wouldn't surprise me if there were a terser way to phrse this.

`{∋ᵈ}ᵐ` is in its own right a fairly suspicious structure – you'd expect to just be able to write `∋ᵈᵐ` – but it doesn't parse for some reason.

# Answer
> 3 votes
# JavaScript (ES6), 99 bytes

Takes input as `(nfa)(string)`. Returns a Set.

```
a=>g=([c,...b],s=[0])=>c?g(b,a.reduce((p,[x,y,z])=>s.includes(x)&y==c?[...p,...z]:p,[])):new Set(s)

```

Try it online!

# Answer
> 3 votes
# Python 3, ~~103~~ 80 bytes

*thanks to @BWO*

```
w=lambda n,f,a={0}:w(n,f[1:],{y for(x,c,y)in n if c==f[0]and{x}&a})if''<f else a

```

TIO

Previous "elegant" list comprehension(103 bytes):

```
def w(a,b):
    q=[0]
    for c in b:q=[j for s in q for i in a if s in i if i[1]==c for j in i[2]]
    return q

```

# Answer
> 3 votes
# , 81 bytes

```
function(a,b,e,s)Reduce(function(A,x)unique(e[a%in%A&b==x]),el(strsplit(s,"")),0)

```

Try it online!

Straightforward answer using `Reduce`. Takes rules as three vectors of `state, symbol, new-states` called `a,b,e`.

Rules are separate (eg. rule `0,'a',[1,2]` is `0,'a',1` and `0,'a',2`).

# Answer
> 2 votes
# Coconut, 64 bytes

```
d->reduce$((s,c)->{r for(*y,r)in d for S in s if[S,c]==y},?,{0})

```

Try it online!

# Answer
> 2 votes
# Clean, 68 bytes

This one based on ovs's Haskell solution is a bit shorter than my initial approach was.

*now includes a test harness*

```
import StdEnv
?d=foldl(\s c=removeDup[r\\(y,r)<-d,g<-s|(g,c)==y])[0]

```

Try it online!

# Answer
> 1 votes
# Perl 6, ~~61~~ 54 bytes

```
->\n,\s{set +s&&reduce {n.grep(*[^2]⊆@_)[*;2]},0,|s}

```

Try it online!

Takes a list of state transitions and an input string as list of characters.

# Answer
> 1 votes
# Charcoal, 44 bytes

```
⊞υ⁰Ｆη«≔υζ≔⟦⟧υＦζＦθ¿∧⁼§λ⁰κ⁼§λ¹ιＦ§λ²¿¬№υμ⊞υμ»Ｉυ

```

Try it online! Link is to verbose version of code. Explanation:

```
⊞υ⁰

```

Push `0` to the predefined empty list to set the inital state to \\$\\{0\\}\\$.

```
Ｆη«

```

Loop over the input.

```
≔υζ

```

Copy the state.

```
≔⟦⟧υ

```

Reset the state.

```
Ｆζ

```

Loop over the copy of the state.

```
Ｆθ

```

Loop over the NFA entries.

```
¿∧⁼§λ⁰κ⁼§λ¹ι

```

If the entry matches, then...

```
Ｆ§λ²

```

... loop over the new states...

```
¿¬№υμ

```

.... if they are not already in the list...

```
⊞υμ»

```

... add them to the list.

```
Ｉυ

```

Cast the list of states to string for implicit output on separate lines.

# Answer
> 1 votes
# Japt, 31 bytes

```
W=[W]c;Ê?ßUÅVVf!øW føUg)mÌc):Wâ

```

Try it!

Saved 2 bytes with better use of Japt's ability to implicitly form a function out of some inputs

Explanation:

```
W=[W]c;                            Initialize the state set to [0] on the first run
       Ê?                   :Wâ    If the input is empty return the unique states; else...
             Vf!øW                 Get the transitions valid for one of the current states
                   føUg)           Of those, get the ones valid for the current character
                        mÌc)       Merge the states of the remaining transitions
         ßUÅV                      Repeat with the remaining characters as input

```

The new "initialize states" code could use a bit more detail. Japt initializes `W` to 0 if there are fewer than 3 inputs, so on the first run `[W]` is `[0]`, and `c` "flattens" an array. `[0]` is already as flat as it gets, so it isn't changed. On subsequent runs `W` has a different value, for example `[1,2]`. In that case `[W]` becomes `[[1,2]]`, a single-element array where that element is an array. This time `c` unwraps that and gets back to `[1,2]`. Thus, on the first run it's `W=[0]` and on subsequent runs it's `W=W`.

---
Tags: code-golf, string, graph-theory
---


# Question
Title: Build an EBCDIC converter using NAND logic gates
In this question, a mapping is defined between EBCDIC and a superset of ISO-8859-1.

Your task is to build a network of two-input NAND gates that will take eight inputs `A1, A2, A4, ..., A128` representing an EBCDIC character and return eight outputs `B1, B2, B4, ..., B128` that represent the corresponding "ISO-8859-1" character according to that mapping.

To simplify things, you may use AND, OR, NOT, and XOR gates in your diagram, with the following corresponding scores:

* `NOT: 1`
* `AND: 2`
* `OR: 3`
* `XOR: 4`

Each of these scores corresponds to the number of NAND gates that it takes to construct the corresponding gate.

The logic circuit that uses the fewest NAND gates to correctly implement all the above requirements wins.

# Answer
> 8 votes
### 727 Gates

How I did it:

1. turned the code page translation from wikipedia into an appropriately formatted truth table using Excel (15 minutes)
2. minimized the truth table using Espresso (5 minutes, 30 minutes on 1st iteration getting back into the saddle)
3. fed the minimized truth table into a schematic generator (1 minute)
4. iterated on 2&3 until I got a reasonable answer (\<1 hour)
5. turned the schematic into an uploadable image (30 min, %$#@! Microsoft)

Here's the 100% NAND gate result:

If I was actually going to implement this, I'd drop the NAND-centric scoring. Building XOR gates out of NANDs is a big waste of transistors. Then I'd start worrying about UMC, fire up the FPGA design tools, maybe break out the HDL manuals, etc. Whew! I love software.
NB, for hobbyists interested in FPGAs, I'll recommend FPGA4fun.

# Answer
> 5 votes
#309 NANDs#

A really low solution in the number of NANDs, but I can go even lower. One just have to stop somewhere, some time, and 309 seems good for that.

No pencil drawn image of the circuit this time. Perhaps later if I some day return to this problem and hit a lower edge, ledge, limit, in the increasingly dense thicket of wrong circuits.

The circuit is presented in obvious Verilog code, ready for running with test included.

Verilog code:

```
// EBCDIC to ISO-latin-1 converter circuit
// Made of just 309 NANDs
//
// By Kim Øyhus 2018 (c) into (CC BY-SA 3.0)
// This work is licensed under the Creative Commons Attribution     3.0
// Unported License. To view a copy of this license, visit
// https://creativecommons.org/licenses/by-sa/3.0/
//
// This is my entry to win this Programming Puzzle & Code Golf
// at Stack Exchange:
// https://codegolf.stackexchange.com/questions/26252/build-an-ebcdic-converter-using-nand-logic-gates
//
// There are even simpler solutions to this puzzle,
// but I just had to stop somewhere, and 309 NAND gates is
// a very low number anyway.

module EBCDIC_to_ISO_latin_1 ( in_000, in_001, in_002, in_003, in_004, in_005, in_006, in_007, out000, out001, out002, out003, out004, out005, out006, out007 );
  input  in_000, in_001, in_002, in_003, in_004, in_005, in_006, in_007;
  output out000, out001, out002, out003, out004, out005, out006, out007;
  wire   wir000, wir001, wir002, wir003, wir004, wir005, wir006, wir007, wir008, wir009, wir010, wir011, wir012, wir013, wir014, wir015, wir016, wir017, wir018, wir019, wir020, wir021, wir022, wir023, wir024, wir025, wir026, wir027, wir028, wir029, wir030, wir031, wir032, wir033, wir034, wir035, wir036, wir037, wir038, wir039, wir040, wir041, wir042, wir043, wir044, wir045, wir046, wir047, wir048, wir049, wir050, wir051, wir052, wir053, wir054, wir055, wir056, wir057, wir058, wir059, wir060, wir061, wir062, wir063, wir064, wir065, wir066, wir067, wir068, wir069, wir070, wir071, wir072, wir073, wir074, wir075, wir076, wir077, wir078, wir079, wir080, wir081, wir082, wir083, wir084, wir085, wir086, wir087, wir088, wir089, wir090, wir091, wir092, wir093, wir094, wir095, wir096, wir097, wir098, wir099, wir100, wir101, wir102, wir103, wir104, wir105, wir106, wir107, wir108, wir109, wir110, wir111, wir112, wir113, wir114, wir115, wir116, wir117, wir118, wir119, wir120, wir121, wir122, wir123, wir124, wir125, wir126, wir127, wir128, wir129, wir130, wir131, wir132, wir133, wir134, wir135, wir136, wir137, wir138, wir139, wir140, wir141, wir142, wir143, wir144, wir145, wir146, wir147, wir148, wir149, wir150, wir151, wir152, wir153, wir154, wir155, wir156, wir157, wir158, wir159, wir160, wir161, wir162, wir163, wir164, wir165, wir166, wir167, wir168, wir169, wir170, wir171, wir172, wir173, wir174, wir175, wir176, wir177, wir178, wir179, wir180, wir181, wir182, wir183, wir184, wir185, wir186, wir187, wir188, wir189, wir190, wir191, wir192, wir193, wir194, wir195, wir196, wir197, wir198, wir199, wir200, wir201, wir202, wir203, wir204, wir205, wir206, wir207, wir208, wir209, wir210, wir211, wir212, wir213, wir214, wir215, wir216, wir217, wir218, wir219, wir220, wir221, wir222, wir223, wir224, wir225, wir226, wir227, wir228, wir229, wir230, wir231, wir232, wir233, wir234, wir235, wir236, wir237, wir238, wir239, wir240, wir241, wir242, wir243, wir244, wir245, wir246, wir247, wir248, wir249, wir250, wir251, wir252, wir253, wir254, wir255, wir256, wir257, wir258, wir259, wir260, wir261, wir262, wir263, wir264, wir265, wir266, wir267, wir268, wir269, wir270, wir271, wir272, wir273, wir274, wir275, wir276, wir277, wir278, wir279, wir280, wir281, wir282, wir283, wir284, wir285, wir286, wir287, wir288, wir289, wir290, wir291, wir292, wir293, wir294, wir295, wir296, wir297, wir298, wir299, wir300, wir301, wir302;

  nand gate000 ( wir000, in_003, in_000 );
  nand gate001 ( wir001, in_002, in_002 );
  nand gate002 ( wir002, in_000, in_000 );
  nand gate003 ( wir003, in_000, in_004 );
  nand gate004 ( wir004, wir003, in_001 );
  nand gate005 ( wir005, in_006, in_003 );
  nand gate006 ( wir006, wir003, wir005 );
  nand gate007 ( wir007, in_007, in_007 );
  nand gate008 ( wir008, wir003, wir004 );
  nand gate009 ( wir009, wir003, wir006 );
  nand gate010 ( wir010, in_005, wir009 );
  nand gate011 ( wir011, wir008, wir009 );
  nand gate012 ( wir012, wir009, wir011 );
  nand gate013 ( wir013, in_004, wir002 );
  nand gate014 ( wir014, wir013, wir009 );
  nand gate015 ( wir015, in_006, wir007 );
  nand gate016 ( wir016, wir001, wir015 );
  nand gate017 ( wir017, wir015, wir015 );
  nand gate018 ( wir018, in_003, wir015 );
  nand gate019 ( wir019, wir018, wir018 );
  nand gate020 ( wir020, wir000, wir007 );
  nand gate021 ( wir021, wir005, wir017 );
  nand gate022 ( wir022, wir018, wir011 );
  nand gate023 ( wir023, in_002, wir018 );
  nand gate024 ( wir024, in_001, in_003 );
  nand gate025 ( wir025, wir010, in_004 );
  nand gate026 ( wir026, wir017, wir024 );
  nand gate027 ( wir027, wir001, wir007 );
  nand gate028 ( wir028, in_004, wir024 );
  nand gate029 ( wir029, wir024, wir024 );
  nand gate030 ( wir030, in_004, wir023 );
  nand gate031 ( wir031, wir022, wir030 );
  nand gate032 ( wir032, wir026, wir030 );
  nand gate033 ( wir033, wir030, wir020 );
  nand gate034 ( wir034, wir001, wir026 );
  nand gate035 ( wir035, wir022, in_007 );
  nand gate036 ( wir036, wir020, wir034 );
  nand gate037 ( wir037, wir007, wir023 );
  nand gate038 ( wir038, wir034, wir023 );
  nand gate039 ( wir039, wir031, wir033 );
  nand gate040 ( wir040, wir028, wir019 );
  nand gate041 ( wir041, wir036, wir040 );
  nand gate042 ( wir042, in_001, wir025 );
  nand gate043 ( wir043, wir041, wir010 );
  nand gate044 ( wir044, wir038, wir000 );
  nand gate045 ( wir045, wir033, wir004 );
  nand gate046 ( wir046, wir039, wir045 );
  nand gate047 ( wir047, in_002, wir046 );
  nand gate048 ( wir048, wir011, wir037 );
  nand gate049 ( wir049, wir012, in_006 );
  nand gate050 ( wir050, wir048, wir007 );
  nand gate051 ( wir051, wir048, wir049 );
  nand gate052 ( wir052, in_006, in_004 );
  nand gate053 ( wir053, wir043, wir001 );
  nand gate054 ( wir054, wir042, wir053 );
  nand gate055 ( wir055, wir019, wir007 );
  nand gate056 ( wir056, wir016, wir039 );
  nand gate057 ( wir057, in_003, wir026 );
  nand gate058 ( wir058, wir029, in_007 );
  nand gate059 ( wir059, in_005, wir055 );
  nand gate060 ( wir060, wir035, wir054 );
  nand gate061 ( wir061, wir055, wir060 );
  nand gate062 ( wir062, wir032, in_003 );
  nand gate063 ( wir063, wir002, wir059 );
  nand gate064 ( wir064, wir062, wir025 );
  nand gate065 ( wir065, wir063, wir036 );
  nand gate066 ( wir066, wir060, wir065 );
  nand gate067 ( wir067, wir037, wir065 );
  nand gate068 ( wir068, wir029, in_006 );
  nand gate069 ( wir069, wir067, wir043 );
  nand gate070 ( wir070, wir061, wir069 );
  nand gate071 ( wir071, wir047, wir070 );
  nand gate072 ( wir072, wir071, wir071 );
  nand gate073 ( wir073, wir071, wir038 );
  nand gate074 ( wir074, wir010, wir073 );
  nand gate075 ( wir075, wir021, wir038 );
  nand gate076 ( wir076, wir028, wir066 );
  nand gate077 ( wir077, wir076, wir056 );
  nand gate078 ( wir078, wir077, wir077 );
  nand gate079 ( wir079, wir072, wir013 );
  nand gate080 ( wir080, wir079, wir026 );
  nand gate081 ( wir081, wir080, wir080 );
  nand gate082 ( wir082, wir078, wir025 );
  nand gate083 ( wir083, wir022, wir082 );
  nand gate084 ( wir084, in_001, wir083 );
  nand gate085 ( wir085, wir044, wir083 );
  nand gate086 ( wir086, wir085, wir081 );
  nand gate087 ( wir087, wir027, wir086 );
  nand gate088 ( wir088, wir087, wir007 );
  nand gate089 ( wir089, wir074, wir087 );
  nand gate090 ( wir090, wir051, wir075 );
  nand gate091 ( wir091, wir068, wir089 );
  nand gate092 ( wir092, wir091, wir091 );
  nand gate093 ( wir093, wir084, wir002 );
  nand gate094 ( wir094, wir051, wir091 );
  nand gate095 ( wir095, wir094, wir042 );
  nand gate096 ( wir096, wir021, wir094 );
  nand gate097 ( wir097, wir093, wir096 );
  nand gate098 ( wir098, wir096, wir044 );
  nand gate099 ( wir099, wir063, wir096 );
  nand gate100 ( wir100, wir088, wir026 );
  nand gate101 ( wir101, wir090, wir099 );
  nand gate102 ( wir102, wir101, wir101 );
  nand gate103 ( wir103, wir100, wir066 );
  nand gate104 ( wir104, wir057, wir102 );
  nand gate105 ( wir105, wir102, wir092 );
  nand gate106 ( wir106, wir102, wir059 );
  nand gate107 ( wir107, wir038, wir103 );
  nand gate108 ( wir108, wir072, wir102 );
  nand gate109 ( wir109, wir108, wir052 );
  nand gate110 ( wir110, wir052, wir021 );
  nand gate111 ( wir111, wir100, wir110 );
  nand gate112 ( wir112, wir110, wir106 );
  nand gate113 ( wir113, wir109, wir112 );
  nand gate114 ( wir114, wir104, wir038 );
  nand gate115 ( wir115, in_007, wir113 );
  nand gate116 ( wir116, wir060, wir115 );
  nand gate117 ( wir117, wir115, wir058 );
  nand gate118 ( wir118, wir117, wir038 );
  nand gate119 ( wir119, wir117, wir117 );
  nand gate120 ( wir120, wir116, in_006 );
  nand gate121 ( wir121, wir093, wir081 );
  nand gate122 ( wir122, wir119, wir120 );
  nand gate123 ( wir123, wir120, wir002 );
  nand gate124 ( wir124, wir119, in_007 );
  nand gate125 ( wir125, wir052, wir120 );
  nand gate126 ( wir126, wir120, wir020 );
  nand gate127 ( wir127, wir020, wir126 );
  nand gate128 ( wir128, wir126, wir124 );
  nand gate129 ( wir129, wir128, wir106 );
  nand gate130 ( wir130, wir100, wir104 );
  nand gate131 ( wir131, in_007, wir128 );
  nand gate132 ( wir132, wir061, wir128 );
  nand gate133 ( wir133, wir064, wir050 );
  nand gate134 ( wir134, wir068, wir093 );
  nand gate135 ( wir135, wir134, wir044 );
  nand gate136 ( wir136, wir127, wir121 );
  nand gate137 ( wir137, wir095, wir136 );
  nand gate138 ( wir138, wir105, wir137 );
  nand gate139 ( wir139, wir058, wir138 );
  nand gate140 ( wir140, wir138, wir118 );
  nand gate141 ( wir141, wir078, wir131 );
  nand gate142 ( wir142, wir140, wir140 );
  nand gate143 ( wir143, wir129, wir140 );
  nand gate144 ( wir144, wir129, wir109 );
  nand gate145 ( wir145, wir090, in_005 );
  nand gate146 ( wir146, wir145, wir145 );
  nand gate147 ( wir147, wir133, wir059 );
  nand gate148 ( wir148, wir093, wir147 );
  nand gate149 ( wir149, wir148, wir148 );
  nand gate150 ( wir150, wir131, wir131 );
  nand gate151 ( wir151, wir143, wir116 );
  nand gate152 ( wir152, wir021, wir132 );
  nand gate153 ( wir153, wir144, wir051 );
  nand gate154 ( wir154, wir122, wir149 );
  nand gate155 ( wir155, wir149, wir142 );
  nand gate156 ( wir156, in_001, wir149 );
  nand gate157 ( wir157, wir123, wir098 );
  nand gate158 ( wir158, wir058, wir133 );
  nand gate159 ( wir159, in_007, wir158 );
  nand gate160 ( wir160, wir133, wir157 );
  nand gate161 ( wir161, wir129, wir159 );
  nand gate162 ( wir162, wir059, wir100 );
  nand gate163 ( wir163, wir130, wir159 );
  nand gate164 ( wir164, wir152, wir146 );
  nand gate165 ( wir165, wir164, wir155 );
  nand gate166 ( wir166, wir121, wir164 );
  nand gate167 ( wir167, wir166, wir157 );
  nand gate168 ( wir168, wir167, wir058 );
  nand gate169 ( wir169, wir059, wir104 );
  nand gate170 ( wir170, wir139, wir169 );
  nand gate171 ( wir171, wir135, wir168 );
  nand gate172 ( wir172, wir171, wir156 );
  nand gate173 ( wir173, wir025, in_004 );
  nand gate174 ( wir174, wir172, wir143 );
  nand gate175 ( wir175, wir000, wir172 );
  nand gate176 ( wir176, wir154, wir172 );
  nand gate177 ( wir177, wir176, wir162 );
  nand gate178 ( wir178, wir111, in_005 );
  nand gate179 ( wir179, in_004, wir144 );
  nand gate180 ( wir180, wir162, wir178 );
  nand gate181 ( wir181, wir173, wir141 );
  nand gate182 ( wir182, wir180, wir131 );
  nand gate183 ( wir183, wir154, wir182 );
  nand gate184 ( wir184, wir090, wir183 );
  nand gate185 ( wir185, wir184, wir179 );
  nand gate186 ( wir186, wir107, wir058 );
  nand gate187 ( wir187, wir097, wir184 );
  nand gate188 ( wir188, wir016, wir177 );
  nand gate189 ( wir189, wir114, wir188 );
  nand gate190 ( wir190, wir189, wir143 );
  nand gate191 ( wir191, wir109, wir190 );
  nand gate192 ( wir192, wir185, wir190 );
  nand gate193 ( wir193, wir190, in_004 );
  nand gate194 ( wir194, wir193, wir135 );
  nand gate195 ( wir195, wir192, wir165 );
  nand gate196 ( wir196, wir194, wir161 );
  nand gate197 ( wir197, wir161, wir196 );
  nand gate198 ( wir198, wir196, wir185 );
  nand gate199 ( wir199, wir198, wir198 );
  nand gate200 ( wir200, wir155, wir181 );
  nand gate201 ( wir201, wir200, wir119 );
  nand gate202 ( wir202, in_006, wir090 );
  nand gate203 ( wir203, in_001, wir052 );
  nand gate204 ( wir204, wir185, wir202 );
  nand gate205 ( wir205, wir175, wir198 );
  nand gate206 ( wir206, wir205, wir150 );
  nand gate207 ( wir207, wir205, wir200 );
  nand gate208 ( wir208, wir207, wir168 );
  nand gate209 ( wir209, wir208, wir185 );
  nand gate210 ( wir210, wir144, wir199 );
  nand gate211 ( wir211, wir210, wir187 );
  nand gate212 ( wir212, wir210, wir135 );
  nand gate213 ( wir213, wir187, wir144 );
  nand gate214 ( wir214, wir151, wir210 );
  nand gate215 ( wir215, wir143, wir105 );
  nand gate216 ( wir216, wir021, wir215 );
  nand gate217 ( wir217, wir160, wir160 );
  nand gate218 ( wir218, wir186, wir061 );
  nand gate219 ( wir219, wir216, wir025 );
  nand gate220 ( wir220, wir219, wir122 );
  nand gate221 ( wir221, wir212, wir219 );
  nand gate222 ( wir222, wir209, wir105 );
  nand gate223 ( wir223, wir191, wir213 );
  nand gate224 ( wir224, wir168, wir221 );
  nand gate225 ( wir225, wir224, wir224 );
  nand gate226 ( wir226, wir144, wir209 );
  nand gate227 ( wir227, wir020, wir222 );
  nand gate228 ( wir228, wir129, wir226 );
  nand gate229 ( wir229, wir228, wir160 );
  nand gate230 ( wir230, wir229, wir229 );
  nand gate231 ( wir231, wir197, wir230 );
  nand gate232 ( wir232, wir230, wir214 );
  nand gate233 ( wir233, wir173, wir230 );
  nand gate234 ( wir234, wir056, wir174 );
  nand gate235 ( wir235, wir146, wir181 );
  nand gate236 ( wir236, wir235, wir225 );
  nand gate237 ( wir237, wir236, wir014 );
  nand gate238 ( wir238, wir236, wir174 );
  nand gate239 ( wir239, wir155, wir203 );
  nand gate240 ( wir240, wir209, wir236 );
  nand gate241 ( wir241, wir146, wir225 );
  nand gate242 ( wir242, wir191, wir241 );
  nand gate243 ( wir243, wir241, wir209 );
  nand gate244 ( wir244, wir206, wir111 );
  nand gate245 ( wir245, wir243, wir233 );
  nand gate246 ( wir246, wir223, wir234 );
  nand gate247 ( wir247, wir191, wir186 );
  nand gate248 ( wir248, wir056, wir238 );
  nand gate249 ( wir249, wir248, wir218 );
  nand gate250 ( wir250, wir243, wir249 );
  nand gate251 ( wir251, wir239, wir174 );
  nand gate252 ( wir252, wir251, wir231 );
  nand gate253 ( wir253, wir249, wir244 );
  nand gate254 ( wir254, wir240, wir150 );
  nand gate255 ( wir255, wir253, wir139 );
  nand gate256 ( wir256, wir242, wir253 );
  nand gate257 ( wir257, wir244, wir195 );
  nand gate258 ( wir258, wir204, wir201 );
  nand gate259 ( out007, wir254, wir255 );
  nand gate260 ( wir259, wir217, wir253 );
  nand gate261 ( wir260, wir258, wir259 );
  nand gate262 ( wir261, wir197, wir260 );
  nand gate263 ( wir262, wir220, wir261 );
  nand gate264 ( wir263, wir261, wir192 );
  nand gate265 ( wir264, wir262, wir263 );
  nand gate266 ( wir265, wir201, wir125 );
  nand gate267 ( wir266, wir265, wir250 );
  nand gate268 ( wir267, wir266, wir237 );
  nand gate269 ( wir268, wir266, wir199 );
  nand gate270 ( wir269, wir136, wir244 );
  nand gate271 ( wir270, wir264, wir195 );
  nand gate272 ( wir271, wir256, wir268 );
  nand gate273 ( wir272, wir247, wir269 );
  nand gate274 ( wir273, wir271, in_001 );
  nand gate275 ( wir274, wir256, wir271 );
  nand gate276 ( wir275, wir273, wir274 );
  nand gate277 ( wir276, wir275, wir275 );
  nand gate278 ( wir277, wir249, wir227 );
  nand gate279 ( wir278, wir222, in_006 );
  nand gate280 ( wir279, wir278, wir153 );
  nand gate281 ( wir280, wir272, wir163 );
  nand gate282 ( wir281, wir278, wir170 );
  nand gate283 ( wir282, wir245, wir281 );
  nand gate284 ( wir283, wir204, wir282 );
  nand gate285 ( out005, wir283, wir254 );
  nand gate286 ( wir284, wir232, wir201 );
  nand gate287 ( wir285, wir284, wir197 );
  nand gate288 ( wir286, wir257, wir285 );
  nand gate289 ( wir287, out007, wir279 );
  nand gate290 ( wir288, wir163, wir287 );
  nand gate291 ( wir289, wir245, wir288 );
  nand gate292 ( wir290, wir288, wir247 );
  nand gate293 ( wir291, wir252, wir211 );
  nand gate294 ( wir292, wir277, wir232 );
  nand gate295 ( wir293, wir192, wir292 );
  nand gate296 ( wir294, wir290, wir280 );
  nand gate297 ( wir295, wir264, wir292 );
  nand gate298 ( wir296, wir217, wir264 );
  nand gate299 ( wir297, wir221, wir295 );
  nand gate300 ( out003, wir294, wir295 );
  nand gate301 ( wir298, wir273, wir297 );
  nand gate302 ( out002, wir298, wir246 );
  nand gate303 ( out006, wir240, wir289 );
  nand gate304 ( wir299, wir293, wir250 );
  nand gate305 ( out000, wir270, wir267 );
  nand gate306 ( out001, wir276, wir291 );
  nand gate307 ( wir300, wir299, wir296 );
  nand gate308 ( out004, wir286, wir300 );
endmodule

module test;
   reg  [7:0] AB; // C=A*B
   wire [7:0] C;

  EBCDIC_to_ISO_latin_1 U1 (
  .in_000 (AB[0]),
  .in_001 (AB[1]),
  .in_002 (AB[2]),
  .in_003 (AB[3]),
  .in_004 (AB[4]),
  .in_005 (AB[5]),
  .in_006 (AB[6]),
  .in_007 (AB[7]),
  .out000 (C[0]),
  .out001 (C[1]),
  .out002 (C[2]),
  .out003 (C[3]),
  .out004 (C[4]),
  .out005 (C[5]),
  .out006 (C[6]),
  .out007 (C[7])
  );

  initial  AB=0;
  always  #1  AB = AB+1;
  initial  begin
    $display("\t\ttime,\tEBCDIC   \tISO-latin-1");
    $monitor("%d,\t%b %b\t%b %b\t%c",$time, AB[7:4], AB[3:0], C[7:4], C[3:0], C);
  end
  initial  #255  $finish;
endmodule

// iverilog -o EBCDIC_309 EBCDIC_309.v
// vvp EBCDIC_309

/*
https://codegolf.stackexchange.com/questions/24925/ebcdic-code-golf-happy-birthday-system-360

 EBCDIC037_to_Latin1 = [
    0x00,0x01,0x02,0x03,0x9c,0x09,0x86,0x7f,0x97,0x8d,0x8e,0x0b,0x0c,0x0d,0x0e,0x0f,
    0x10,0x11,0x12,0x13,0x9d,0x85,0x08,0x87,0x18,0x19,0x92,0x8f,0x1c,0x1d,0x1e,0x1f,
    0x80,0x81,0x82,0x83,0x84,0x0a,0x17,0x1b,0x88,0x89,0x8a,0x8b,0x8c,0x05,0x06,0x07,
    0x90,0x91,0x16,0x93,0x94,0x95,0x96,0x04,0x98,0x99,0x9a,0x9b,0x14,0x15,0x9e,0x1a,
    0x20,0xa0,0xe2,0xe4,0xe0,0xe1,0xe3,0xe5,0xe7,0xf1,0xa2,0x2e,0x3c,0x28,0x2b,0x7c,
    0x26,0xe9,0xea,0xeb,0xe8,0xed,0xee,0xef,0xec,0xdf,0x21,0x24,0x2a,0x29,0x3b,0xac,
    0x2d,0x2f,0xc2,0xc4,0xc0,0xc1,0xc3,0xc5,0xc7,0xd1,0xa6,0x2c,0x25,0x5f,0x3e,0x3f,
    0xf8,0xc9,0xca,0xcb,0xc8,0xcd,0xce,0xcf,0xcc,0x60,0x3a,0x23,0x40,0x27,0x3d,0x22,
    0xd8,0x61,0x62,0x63,0x64,0x65,0x66,0x67,0x68,0x69,0xab,0xbb,0xf0,0xfd,0xfe,0xb1,
    0xb0,0x6a,0x6b,0x6c,0x6d,0x6e,0x6f,0x70,0x71,0x72,0xaa,0xba,0xe6,0xb8,0xc6,0xa4,
    0xb5,0x7e,0x73,0x74,0x75,0x76,0x77,0x78,0x79,0x7a,0xa1,0xbf,0xd0,0xdd,0xde,0xae,
    0x5e,0xa3,0xa5,0xb7,0xa9,0xa7,0xb6,0xbc,0xbd,0xbe,0x5b,0x5d,0xaf,0xa8,0xb4,0xd7,
    0x7b,0x41,0x42,0x43,0x44,0x45,0x46,0x47,0x48,0x49,0xad,0xf4,0xf6,0xf2,0xf3,0xf5,
    0x7d,0x4a,0x4b,0x4c,0x4d,0x4e,0x4f,0x50,0x51,0x52,0xb9,0xfb,0xfc,0xf9,0xfa,0xff,
    0x5c,0xf7,0x53,0x54,0x55,0x56,0x57,0x58,0x59,0x5a,0xb2,0xd4,0xd6,0xd2,0xd3,0xd5,
    0x30,0x31,0x32,0x33,0x34,0x35,0x36,0x37,0x38,0x39,0xb3,0xdb,0xdc,0xd9,0xda,0x9f];
 */

```

Kim Øyhus

---
Tags: atomic-code-golf, logic-gates
---


title: Is the Circuit Possible?

text:
# Question
Title: Is the Circuit Possible?
Write a program or function that takes input: all resistors available and a resistance value and outputs a truthy value of whether or not it is possible to get the resistance by using those resistors.

**Rules:**

Any format for input will do.

There will be at least 1 available resistor and your program should output for at least 10 available resistors.

Resistance of all available resistors and the required resistance will be positive integers.

For available resistors if a fractional value is also possible, the required resistance may be the approximated value.(See example)

Output should be any 2 unique values for Possible and Not possible.

The resistors may be connected in any manner.

*Series* Resistance: For n resistances in series: Result=R1+R2+R3+....Rn

*Parallel* Resistance: For n resistances in parallel: Result=1/(1/R1+1/R2+1/R3+....+1/Rn)

The circuit may not require all the resistors to get the required resistance (output True if that is the case).

**Winner:**

This is code-golf so shortest-code wins.

**Examples:**

```
R     List
110   220,220 -> True
440   220,220 -> True
550   400,300 -> False
3000  1000,3000 -> True
750   1000,3000 -> True
333   1000,1000,1000 -> True (1000||1000||1000=333.333)
667   1000,1000,1000 -> True ((1000+1000)||1000=666.6666)
8000  1000,1000,7000 -> True
190   100,200,333,344,221 -> True
193   105,200,333,344,221 -> True
400   200,100 -> False

```

Explanation for the last two examples: https://physics.stackexchange.com/questions/22252/resistor-circuit-that-isnt-parallel-or-series

# Answer
# Python 3, 253 bytes

```
import functools
def p(l): return functools.reduce(lambda z,x:z+[y+[x]for y in z],l,[[]])
print(l[-1:][0]in[round(a)for a in[sum(a)for a in p([sum(a)for a in p(l)]+[1/sum(c)for c in[[1/b for b in a if b!=0]for a in p(l).copy()]if sum(c)!=0])]])

```

I take the powerset of all resistor values and then calculate the sums for series and 1/sum(1/values) for paralel and then I take a powerset of these two sets. When you take the sum of all the subsets and put them into a set then this set eiter contains the value or not. -\> return True/False

@stephen thanks :)
> 1 votes

# Answer
# Japt, 52 bytes

```
à má

ÈÊ<2?X:X¯1 ïXÅgW @[X+Y1/(1/XÄ/Y]Ãc
mmW c mr øV

```

Try it!

This was a tough one, and I had to do a couple of strange things to make it work. I can't mathematically prove that this works for everything, but it works for all the test cases as well as my extra proposed test case. Specifically, I know that the function I define called `W` gives different results depending on the order of the resistors in its input so I run it on each possible ordering of each possible combination of resistors. I also know that it will produce a list of resistances that are all possible to create using the input resistors. I don't know with 100% certainty that those two things together end up with every possible resistance.

Explanation:

```
à       Get each combination e.g. [1,2,3] -> [[1,2,3],[1,2],[1,3],[2,3],[1],[2],[3]]
  m     For each combination...
   á    Get each order e.g. [1,2,3] -> [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

    Skip a line to avoid overwriting the target resistance

È                                     Define a function W taking an array input X:
 Ê<2?X                                  If X is only 1 resistor, return it as-is
            XÅgW                        Get the resistances from applying W to the tail of X
       X¯1 ï                            Pair the first resistor with each possible tail resistance
                 @[            ]Ã       For each pair get these two values:
                   X+Y                    Those resistances in series
                      1/(1/XÄ/Y           Those resistances in parallel
                                 c      Collapse all those resistances into a single flat list

mmW            For each combination and order, get the resistances using W
    c          Collapse to a single list of resistances
      mr       Round each one
         øV    Return true if the target resistance is in the list, false otherwise

```
> 1 votes

# Answer
# Ruby, 153 bytes

```
f=->v,r{[r]-v==[]||r[1]&&[*2..v.size].any?{|n|v.permutation.any?{|l|[l[0,n].sum,(1.0/l[0,n].reduce(0){|s,x|s+1.0/x}).round].any?{|b|f[l[n..-1]+[b],r]}}}}

```

Try it online!

Brute force. I mean it.
> 0 votes

---
Tags: code-golf, electrical-engineering
---