previndexinfonext

code guessing, round #44 (completed)

started at ; stage 2 at ; ended at

specification

it's called "letters and numbers" on this side of the world, but I hear we're to play countdown. submissions may be written in any language.

countdown is a game show where players perform certain tasks related to letters and numbers, based on a french game show called "numbers and letters". so the UK decided to call it "countdown". clever.

this problem focuses specifically on the "numbers" part of "lett-- or sorry, "countdown"

...

...in which contestants are given a bag of numeric literals and arithmetic operators and tasked with constructing an expression that evaluates to a target number. the closer your result is to the target, the more points you get!

I will now introduce a simplified version of this game. given a multiset of "objects", which may be numbers from 0 to 9, addition, subtraction, multiplication, or division, and a positive integer target, the goal is to construct an expression as close as possible to the target using only the objects given. note the following caveats:

for example, if the target is 814 and the objects given are {2, 1, 3, 7, 6, 9, +, +, *, *, *, -, /}, the closest answer is (7*2 + 1) * 9 * 6 + 3 = 813.

your challenge, given a string matching [0-9]+[+\-/*]* representing a multiset of objects, and a target number, is to return the closest attainable number to the target. as any language is allowed, there is no fixed API.

results

  1. 👑 luatic +4 -2 = 2
    1. truffle
    2. kimapr
    3. olus2000
    4. LyricLy
  2. olus2000 +4 -4 = 0
    1. truffle
    2. kimapr
    3. LyricLy
    4. luatic
  3. LyricLy +2 -2 = 0
    1. truffle
    2. luatic (was kimapr)
    3. olus2000
    4. kimapr (was luatic)
  4. truffle +2 -3 = -1
    1. LyricLy (was kimapr)
    2. olus2000
    3. kimapr (was LyricLy)
    4. luatic
  5. kimapr +1 -2 = -1
    1. LyricLy (was truffle)
    2. olus2000
    3. luatic (was LyricLy)
    4. truffle (was luatic)

entries

you can download all the entries

entry #1

written by truffle
submitted at
0 likes

guesses
comments 0

post a comment


dir 44
countdown.py ASCII text
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def entry(objects, target):
    o = objects; t = target; from itertools import permutations as x
    a = "".join(a for a in o if a in "0123456789"); q = x; r = eval; p = len
    b = "".join(b for b in o if b in "+-*/"); e = ["{}"]; n = range; s = abs
    g = []; w = g.append; d = a[0]; o = min; c = s(r(d) - t)
    for f in n(o(p(a), p(b) + 1)):
        for h in e:
            v = h.format
            for i in q(a, f + 1):
                j = v(*i, y='{', z='}'); u = j.format
                for k in q(b, f):
                    l = u(*k)
                    try: m = s(r(l) - t)
                    except: continue
                    if m < c: c, d = m, l
            w("(" + h + " {y}{z} {})"); w("({} {y}{z} " + h + ")")
        e.clear(); e.extend(g); g.clear()
    return d

entry #2

written by kimapr
submitted at
2 likes

guesses
comments 0

post a comment


example ASCII text
1
2
814
2 1 3 7 6 9 + + * * * - /
numbers.lua ASCII text
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
#!/usr/bin/env lua
--[[

  USAGE

  as a cli program:
    $ ./numbers.lua --help

  as a module:
    local numbers = require("numbers")

    numbers.solve(
      814, {2, 1, 3, 7, 6, 9, '+', '+', '*', '*', '-', '/'},
      function(msg) -- optional
         io.stderr:write(msg, '\n')
         io.stderr:flush()
      end,
      true -- equivalent to --hard in cli, optional
    ) -- returns 813, {9, 7, 2, '-', '*', 6, '*', 1, '+', 3, '*'}

--]]

local function eval(op, vals, strict)
	if type(op) == "number" then
		return {op, vals}
	else
		local a, b, o
		if not vals or not vals[2] then return end
		vals, a, b = vals[2][2], vals[2][1], vals[1]
		if strict and a < b then return end
		local commutable = false
		if op == '+' then
			o = a + b
			commutable = true
		elseif op == '-' then
			o = a - b
		elseif op == '*' then
			o = a * b
			commutable = true
		elseif op == '/' then
			o = a / b
		end
		o = (math.tointeger and math.tointeger(o)) or o
		if commutable and a < b then return end
		if strict and o % 1 ~= 0 then return end
		return {o, vals}
	end
end

local function copy(t, o)
	o = o or t
	for k, v in pairs(t) do
		o[k] = v
	end
	return o
end

local function flatten(stack)
	local reversed = {}
	while stack do
		table.insert(reversed, stack[1])
		stack = stack[2]
	end
	local out = {}
	for n = #reversed, 1, -1 do
		table.insert(out, reversed[n])
	end
	return out
end

local function stacklen(stack)
	local n = 0
	while stack do
		n = n + 1
		stack = stack[2]
	end
	return n
end

local function search(expr, vals, ops, write, strict)
	for op, count in pairs(ops) do
		local newvals = eval(op, vals, strict)
		if newvals then
			ops[op] = ops[op] - 1
			ops[op] = ops[op] > 0 and ops[op] or nil
			local newexpr = {op, expr}
			if not newvals[2] then
				write(newvals[1], newexpr)
			end
			search(newexpr, newvals, ops, write, strict)
			ops[op] = count
		end
	end
end

local function findmax(target, log)
	local maxdiff = math.huge
	local maxlen = math.huge
	local maxval = nil
	local maxexpr = nil
	return function(val, expr)
		local diff = math.abs(target - val)
		if diff <= maxdiff then
			local len = stacklen(expr)
			if diff < maxdiff or len <= maxlen then
				log(string.format(
					"... %s -> %s",
					table.concat(flatten(expr), " "), val))
				maxval, maxdiff, maxexpr, maxlen = val, diff, expr, len
			end
		end
	end, function()
		return maxval, flatten(maxexpr)
	end
end

local numbers = {}

function numbers.solve(target, oplist, log, hard)
	log = log or function() end
	local ops, write, maxfunc = {}, findmax(target, log)
	for _, op in pairs(oplist) do
		ops[op] = (ops[op] or 0) + 1
	end
	search(nil, nil, ops, write, not hard)
	return maxfunc()
end

do
	local ok, info = pcall(function()
		return debug.getinfo(5)
	end)
	if not ok or info then
		return numbers
	end
end

local usage = [[
Usage: numbers.lua [OPTION]... [FILE]
Solve a game of countdown.

With no FILE, or when FILE is -, read standard input.

  -q, --quiet, --silent    do not display intermediate results
  -h, --hard               allow fractions and negative numbers
      --help        display this help and exit

GNU coreutils online help: <https://www.gnu.org/software/coreutils/>
Full documentation <https://www.gnu.org/software/coreutils/numbers.lua>
or available locally via: info '(coreutils) numbers.lua invocation'
]]

local file = io.stdin
local istty = os.execute("tty >/dev/null")
istty = (type(istty) == "boolean" and {istty} or {istty == 0})[1]
local log = function(msg)
	io.stderr:write(msg, '\n')
	io.stderr:flush()
end
local hard = false

local options = {
	function(arg)
		if arg == "-" then
			file = io.stdin
		else
			file = assert(io.open(arg))
			istty = false
		end
	end,
	help = function()
		io.stdout:write(usage)
		os.exit(0)
	end,
	quiet = function()
		log = function() end
		istty = false
	end,
	hard = function()
		hard = true
	end,
}

local short_options = {
	q = options.quiet,
	h = options.hard,
}

local args = {...}
local args_done = false
for _, arg in ipairs(args) do
	if not args_done then
		if arg == "--" then
			args_done = true
		elseif string.sub(arg,1,2) == "--" and #arg>2 then
			assert(options[string.sub(arg,3)], "unknown option: " .. arg)()
		elseif string.sub(arg,1,1) == "-" and #arg>1 then
			string.gsub(string.sub(arg,2), '.', function(char)
				assert(short_options[char], "unknown option: -" .. char)()
			end)
		else
			options[1](arg)
		end
	else
		options[1](arg)
	end
end

local function test(target, ops, hard)
	local start = os.clock()
	local val, expr = numbers.solve(target, ops, log, hard)
	log(string.format("done in %.2fs", os.clock() - start))
	print(string.format("%s -> %s", table.concat(expr," "), val))
end

local function input(prompt)
	if istty then
		io.stderr:write(prompt .. "> ")
		io.stderr:flush()
	end
	return (assert(file:read(), "unexpected EOF"))
end

local function parse(str)
	local t = {}
	for v in string.gmatch(str, "%S+") do
		v = tonumber(v) or v
		table.insert(t, v)
	end
	return t
end

test(tonumber(input("target")), parse(input("ops")), hard)

entry #3

written by olus2000
submitted at
1 like

guesses
comments 0

post a comment


entry.prick ASCII text
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
API:
	input on stack from top:
	target,
	length N,
	N ascii-encoded characters from "0123456789+-*/"
	return value on top of stack after termination

memory layout:
	0: target
	1: length of input N
	2: best fit
	3: addr of permutation counting
	4: maximum amount of eval steps
	5-N+4: permutation of input
	N+5-2N+4: permutation counting

method:
	go through permutations of input interpretting them
	update the best fit on every possible intermediate value
	backtrack on stack/value underflow or division error
	permutations are generated using a bad version of heaps algorithm
	pruning is done based on stack size and arguments, all operations fail if the bigger argument is on top
	has very bad complexity if given too many digits and bad complexity overall
	will not execute the example in reasonable time

interpreter:
	asumes all the featured discussed on the wiki:
		builtin functions
		second stack
		number words
	unknown words are noops
	first two you can add to any interpreter using the code on the wiki

: comment


0 @	: target	1 @ : length
2	: best	3 @	: perm	4 @	: steps
5	: input

48	: '0'	43	: '+'	45	: '-'	42	: '*'	47	: '/'

>aux * aux> -- 1	: handle_mul

>aux + aux> -- 1	: handle_add

>aux - aux> -- 1	: handle_sub

-- >aux 1 over 1 [ | drop over over / dup >aux * - 1 swap 1
	[ | drop aux> drop aux> -- 0 0 0 ] [ 1 | aux> aux> 1 ] 0 0
] [ 1 | drop aux> 0 ]	: handle_div

1 over 1 [ '-' - | drop drop handle_div 0 0 0 ]
over over [ '+' - | drop drop handle_sub 0 0 0 ]
over over [ '*' - | drop drop handle_add 0 0 0 ]
[ | handle_mul 0 ]	: handle_operator

target over - over target - + target best @ - best @ target - + swap - 1 [ | best ! 0 0 ] drop	: is_best

best @ 0 input -- >aux 1 steps [ | aux> ++ dup >aux @
	1 over 1 [ '/' - | drop '0' - swap >aux over over swap - aux@ * 1 swap 1
    	[ | drop drop aux> 0 0 0 ] [ 1 | aux> ++ 1 ] 0 0
    ]
	[ 1 | >aux >aux over over - aux> swap over -- * aux> swap dup 1 [ | drop handle_operator 0 swap 0 ] swap drop ]
	>aux over is_best aux>
] ++ [ 1 | drop ] aux>	: eval

perm over - dup dup 2 / 2 * - 1
[ | swap ++ dup @ >aux swap 2 - [ 1 | dup ++ swap over @ swap ! ] aux> swap ! 0 0 0 ]
drop drop	: skip_after

dup >aux ++ input -
[ 1 perm aux@ - dup 2 / 2 * - [ 1 | drop perm -- @ aux@ dup @ perm -- ! ! 0 ]
	[ 1 | aux@ @ perm aux@ length + @ - -- dup @ aux@ ! ! ]
	aux@ length + dup @ ++ dup rot ! ++ perm aux@ - - | 0 aux@ length + ! aux> -- >aux
] aux>	: next_state

eval dup skip_after next_state	: step

1 dup rot [ 1 | >aux aux@ * aux> ++ ] drop	: factorial

0 5 target - 1 [ | drop 9 0 ]	: worst_fit

1 input >aux length [ 1 | 2 + aux> dup ++ >aux @ '/' - 1 [ | 2 - 0 ] ] aux> drop dup length - -	: calculate_steps


0 ! dup 1 ! dup 5 + 3 !

input swap [ 1 | >aux aux@ ! aux> ++ ] drop

calculate_steps 4 !

worst_fit best !

input length factorial [ 4 - | step ]

best @

entry #4

written by LyricLy
submitted at
0 likes

guesses
comments 0

post a comment


answer.py ASCII text
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from collections import Counter

OPS = {
    "+": lambda x, y: x + y,
    "-": lambda x, y: x - y if x >= y else None,
    "*": lambda x, y: x * y,
    "/": lambda x, y: x // y if y and not x % y else None,
}

def results(digits, ops):
    for digit in digits:
        yield digit, digits - Counter({digit: 1}), ops
    for op in ops:
        for r1, digits1, ops1 in results(digits, ops - Counter({op: 1})):
            for r2, digits2, ops2 in results(digits1, ops1):
                final = OPS[op](r1, r2)
                if final is not None:
                    yield final, digits2, ops2

def entry(target, bag):
    digits = Counter()
    i = 0
    while i < len(bag) and bag[i].isdigit():
        digits[int(bag[i])] += 1
        i += 1
    ops = Counter(bag[i:])
    return min(results(digits, ops), key=lambda r: abs(r[0] - target))[0]

entry #5

written by luatic
submitted at
0 likes

guesses
comments 0

post a comment


countdown.py ASCII text
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#programmer time (MY TIME) is worth MOAR than cpu time!!!!!!
import argparse
from collections import Counter
from itertools import permutations,product
class Param:
	n=1
	def eval(it): return next(it)
class Expr:
	def __init__(self,l,op,r):
		self.l,self.op,self.r,self.n=l,op,r,l.n+r.n
	def eval(self,it):
		l,r=self.l.eval(it),self.r.eval(it)
		match self.op:
			case '+': return l+r
			case '*': return l*r
			case '-': return float('nan') if l<r else l-r
			case '/': return float('nan') if not r or l%r else l/r
class Bag:
	def __init__(self,s):
		self.ops=Counter()
		self.digits=Counter()
		for c in s:
			if c in '+-*/':
				self.ops.update((c,))
			elif (d:=ord(c)-ord('0')) in range(10):
				self.digits.update((d,))
			else:
				raise ValueError('invalid string')
	def _exprs(ops):
		yield Param
		if not any(ops.values()): return
		nz=[o for o in ops if ops[o]]
		if sum(1 for _ in nz)==1 and (op:=nz[0]) in '+*':
			e=Param
			for _ in range(ops[op]):
				yield (e:=Expr(e,op,Param))
			return
		for op in ops:
			ops[op]-=1
			for splt in product(*(range(ops[o]+1) for o in ops)):
				for l,r in product(Bag._exprs({o:n for n,o in zip(splt,ops)}),Bag._exprs({o:ops[o]-n for n,o in zip(splt,ops)})):
					yield Expr(l,op,r)
			ops[op]+=1
	def exprs(self): return Bag._exprs(self.ops)
	def params(self,n): return permutations(self.digits,r=n)
	def solve(self,num): return min((expr.eval(iter(params)) for expr in self.exprs() for params in self.params(expr.n)),key=lambda x:abs(num-x))
if __name__=='__main__':
	parser=argparse.ArgumentParser()
	parser.add_argument('bag')
	parser.add_argument('num')
	args=parser.parse_args()
	print(Bag(args.bag).solve(int(args.num)))
ink.jpg JPEG image data, JFIF standard 1.01, resolution (DPI), density 300x300, segment length 16, progressive, precision 8, 4160x3120, components 3