TransWikia.com

Which languages are optimal for problems that require "reading" input while also writing to it like a stack

Code Golf Asked on October 27, 2021

When encountering a problem whose input is meant to be read sequentially, but you may also want to push back onto the input like a stack, which languages have the optimal boilerplates for doing so, and how?

For example, from Create a Boolean Calculator, we have a string like:

1AND0OR1XOR1

We want to "pop" 5 chars 1AND0, compute it to be 0, then "push" it back to form:

0OR1XOR1

Then, repeat until there’s only 1 char left. In this case:

0

It’s trivial to write while loops and such, but this seems common enough in codegolf problems that there must be canonical forms. I wasn’t able to find a question specifically about this setup though, and going through each question by language was difficult.

One Answer

The approach you're asking seems like reduce/left fold in general. Many languages have this, such as Python (reduce(f,seq) or functools.reduce(f,seq)), APL (f⍨/⌽seq), Jelly (f/seq), and Haskell (foldl f start seq).

As a Python example, let's assume we already have the input parsed as a list seq=[1, 'AND', 0, 'OR', 1, 'XOR', 1]. Then reduce(f,seq) is equivalent to

f(f(f(f(f(f(1, 'AND'), 0), 'OR'), 1), 'XOR'), 1)

The trouble here is that we need to take 3 arguments at a time. A way this could be done is by grouping most of the sequence into pairs seq2=[1, ['AND',0], ['OR',1], ['XOR',1]], so reduce(f,seq) would be equivalent to

f(f(f(1, ['AND',0]), ['OR',1]), ['XOR',1])

This could work well in Jelly because it has a builtin s that could help split into pairs (output looks funny strings are internally lists of chars).

However, a loop-based approach would work better in Python by assigning to a slice of an array:

seq=[1, 'AND', 0, 'OR', 1, 'XOR', 1]
while len(seq)>1:
  seq[1:3] = [f(*seq[1:3])]
print(seq[0])

This would output f(f(f(1, 'AND', 0), 'OR', 1), 'XOR', 1).

As @AdHocGarfHunter notes in the comments, recursion is a good idea too:

# (ungolfed)
def r(s):
  if len(s)>1:
    return r(f(*s[:3]) + s[3:])
  else:
    return s[0]

APL has little boilerplate for this: {1=⍴⍵:⊃⍵⋄∇(3↓⍵),f3↑⍵} ( is the recursion). Jelly does too, with 1 byte recursion.

Answered by fireflame241 on October 27, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP